迪杰斯特拉path数组记录什么

今天我们要讲的内容是单元最短路径狄杰斯特拉算法。 假期来了，小曼，我打算去海南旅行，如果出发地北京和目的地海南之间有多条路径，不同的路径有不同的中转城市， 城市之间如果可以通行，通行的路程是已知的，那么从北京到海南的最短距离是多少呢？ 举个例子，从北京出发到海南有三条旅行线路，我们可以途经济南或者是武汉到海南，也可以直达海南。其中北京到济南 的路程是一百公里，济南到海南八百公里，北京到武汉是五百公里，再到海南是六百公里，北京直达海南是一千三百公里。 这里面我们要注意，由于旅行线路不是直线距离，所以有可能北京直达海南的距离更长。 经过计算，如果先到济南再到海南，总距离是九百公里。如果途经武汉到海南，距离是一千一百公里，所以旅行的最短距离方案是从北京途经济南再到海南。 如果说从北京到海南之间还有更多的城市，我们已知可以互相到达的城市之间的路程，那么如 何计算北京到海南的最短距离呢？ 在解决这个问题之前，我们先来学习一下图论的基础知识。 图是由若干顶点以及连接两点之间的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点表示事物，连接两点的线就表示相应两个事物之间的关系。 使用图来描述实际问题的时候，对于连接两顶点的边，往往还需要用一个数值来描述，比如说距离啊，耗费啊，时间等等。一般这个值我们称为全值，带全值的图就称为是带全图。 那么现在呢，我们回到旅行的这个问题，我们可以把这个问题抽象的想象成一张图， 图的顶点代表城市，两个城市之间如果可以通行，相应的两个顶点之间有一条边，边上的全职就代表路程的长度。 我们使用二维数组来存储图，该二维数组也被称为是图的临街矩阵。设这个数组为 graph。 举个例子，如果有零一、二三这四个城市需要表示，那么二位数组的行与列就是从零到三。假设城市零和二之间有一条道路，道路的长度是二，那么 graph 零二等于二。由于往返的距离是一样的，所以 graph 二零等于二。 如果城市零与三之间没有道路，那么格尔夫零三等于无穷大，这里正无穷，可以用一个非常大，大到实际中不会出现的数字来代替，比如说八个九九九九九九九九九， 那么旅行问题就变成了已知一个 n 个顶点的代全图。假设顶点零代表北京，顶点 n 减一代表海南 球，从顶点零出发到顶点 n 减一的最短路径，这是一个经典算法问题。一般呢，我们称为 单元最短路径，也就是从一个顶点出发，计算从这个顶点到其他所有顶点的最短路径长度，这里的长度就是路上各边的全职之和。 这个问题是由荷兰的计算机科学家狄杰斯特拉在一九五九年提出的经典算法，后来呢，这个算法被人们称为是狄杰斯特拉算法，就是用于解决单元最短路径的问题。 狄杰斯特拉算法是基于贪心思想，从起始位置出发，每次寻找与起始距离最近并且没有访问过的顶点，以该顶点作为中间节点更新。从起点到其他 他顶点的距离，直到全部顶点都作为了中间节点，并且完成了路径更新，算法就结束了。举个例子，其实点是北京，我们希望求出北京到海南的最短路径， 北京就是单元最短路径当中的单元。使用狄杰斯特拉算法，我们可以求出北京到其他城市的全部的最短路径。 这里呢，我们用黄色来标记起始位置，用绿色来标记未被访问的节点，用蓝色标记已经作为了中间节点，并且完成了其他顶点的路径更新的节点。 从图中我们可以看到，北京到济南一百公里，到武汉五百公 公里，没有办法直接到达海南。由于北京到济南的距离是最短的，所以首先将济南作为中间节点 更新从北京到其他顶点的距离。从济南可以到达武汉，距离是三百公里，所以北京到武汉的距离就被更新为四百。完成更新之后，济南就被标记为以访问了。 这一轮更新之后，没有被访问，并且距离北京最近的节点是武汉。将武汉作为中间节点更新从北京到其他城市的距离。 从武汉可以到达海南，距离是两百公里，所以北京到海南的距离就被更新为了六百公里， 然后我们将武汉标记为蓝色。最后呢，使用海南作为中间节点来进行路径更新。 由于海南是最后一个顶点，路径更新呢就结束了，我们也求出了北京到武汉、济南、海南这三个城市的最短路径。 现在呢，我们来看一个完整的迪杰斯特拉算法设计。首先，设置 visit 数组标记顶点是否已经作为中间节点完成相应的路径更新。 设置 days 的数组，存储从起始节点到其他节点的最短路径的距离。举个例子，最初呢，我们将起始节点北京对应的 visit 零 标记为一，其余节点的 visit 为零。这样呢，后续北京就不作为中间节点进行路径更新了，而 dist 数组初始化为北京至其他城市的距离就是零五百一百，与众无穷。 进入寻找最短路径的更新循环，由于图中有 n 个顶点，所以最多循环 n 次 寻找中间节点，并且更新从起点到其他节点的最短路径。实际上，除去起始节点和最后一个节点， 循环 n 减二，也就完成了全部路径的更新。比如说北京、武汉、济南、海南这张图，循环两次就可以完成全部城市的 最短路径更新了。在循环当中，设置变量 midst， 存储从起点到其他未被访问节点中的最短距离 电量咪斗存储最短距离节点的编号。循环 n 个顶点，寻找当前未被访问节点中的最短距离与节点编号。比如说当前武汉、济南、海南没有被访问， 其中北京至济南的距离最短，所以循环结束之后， mindest 更新为一百， mido 更新为济南对应的顶点编号。二， 找到距离起始节点最短距离的节点后，以该节点作为中间节点再循环，便利其他所 所有节点。如果说便利的节点未曾作为过中间节点，即 visit 为零，并且从起始节点到该节点的距离大于从起始节点到中间节点与从中间节点到该节点的距离和， 则更新起始节点到该节点的距离更新为起始到中间节点与中间节点到该节点的距离和。 比如说，我们把济南选定为中间节点之后，便利剩下的城市，武汉、海南。由于北京到武汉的距离五百，大于北京到济南与济南到武汉的距离和四百， 所以说将北京到武汉的距离更新为四百，更新后的 dist 为 零，四百一百正无穷，并且将中间节点标记为夷，访问 visit mido 为一。 当全部的节点都作为了中间节点，更新起始节点到其他节点的距离之后，算法就结束了。最终，类似的数组存储了从起始城市到其他全部城市的最短距离。 算法到这里我们就讲完了，现在呢，我们再来看一个更复杂的例子， 以北京为起始点，求到其他城市的最短距离使用绿色标记，未被访问的节点 visit 为零，使用蓝色标记。正在作为中间节点的节点使用黄色标记。已完 完成访问的节点 visit 为一。首先初始化北京到其他城市的距离存储到 dest 数组当中， 选择当前距北京最近的天津作为中间节点，更新北京到其他城市的距离。 更新前，北京到郑州的距离是一千二。由于北京到天津是一百，天津到郑州是九百， 一百加九百小于一千二，所以说北京到郑州的距离更新为一千。同理，北京到济南的距离更新为四百， 这时候没有作为中间节点的城市是济南、郑州、长沙、海南。这起 中呢，距离北京最近的城市是济南，所以我们将济南作为中间城市，更新北京到其他城市的距离。 经过济南到达郑州的距离是四百加四百，就是八百公里，比刚刚经过天津到郑州的距离是更短的，所以北京到郑州的距离更新为八百。 同理，通过济南还可以到达长沙与海南，最终计算出北京到长沙的距离是一千七百公里，到海南是一千八百公里。 这个时候我们再从未标记的城市，郑州、长沙、海南当中选择距离最短的郑州更新到长沙。海南的距离。当前北京到郑州是八百公里， 郑州到长沙是五百公里，八百加五百小于一千七，所以到长沙的距离就更新为一千三百公里，而郑州没有办法到达海南，所以到海南的距离没有更新。 这个时候没有被标记的城市是长沙与海南，长沙到北京的距离更近，所以选择长沙作为中间节点。 由于当前北京到海南的距离是一千八百公里，小于经过长沙到海南的距离，所以不需要通过长沙更新路径，将长沙标记为以访问就可以了。 最后呢，还剩下海南没有作为中间节点来进行路径更新，由于海南是最 最后一个城市，将海南标记为以访问算法就结束了。最终呢，类似的数组当中就存储了北京到其他城市的最短距离。 最后我们再来讲解一下狄杰斯特拉算法的代码实现。首先设计算法的接口，狄杰斯特拉函数传入两个参数，二维向量 graff 代表图的临街矩阵整数 start 代表起始顶点编号 函数返回一个一维项链，存储起始顶点到其他顶点的最短路径。 比如说传入刚刚例子当中的图对应的二维项链 groff， 起始顶点是零函数，经过计算得到结果 的数组返回，也就是北京到其他各个城市的最短路径。 来看一下迪杰斯特拉的具体实现。首先设置变量 n， 存储图中的顶点个数，设置 vz 的数组标记，以作为中间节点完成访问的顶点，设置类似的数组 存储从起点 start 到其他顶点的最短路径。通过循环将 this 的数组初始化为最初图中的路径长度，标记起始顶点 visit start 设置一， 然后进入更新最短路径的循环。循环进行 n 次，在循环当中设置变量 mendist， 存储从起点到其他未被访问 节点中的最短距离处，使为一个最大值变量咪斗存储最短距离节点的编号。 进入第一个二层循环，便利 n 个顶点寻找当前未被访问的顶点中的距离起始顶点最短距离的接点编号 在循环当中，如果 visit g 等于零，说明顶点 g 被被访问，并且 mendest 大于 destg 时，更新最短距离。 mendaced 为 destg 与顶点编号 middle 为 g。 进入第二个二层循环，以 mido 为中间节点循环更新其他所有节点。 如果当前便利的节点 g 未曾作为过中间节点，也就是 visit g 等于零， 且从起始节点到 g 的距离。类似的 g 大于从起始节点到 mido 与从 mido 到 g 的距离和， 则更新起始节点到 g 的距离。 datest g 更新为起始到 middle 与 middle 到 g 的距离合，也就是 datest middle 加 graph middle g 完成了更新之后，将 middle 顶点设置为以访问 visit middle 等于一。 完成了 n 次最短路径更新后，算法就结束了，最终返回最短路径，结果数组对死他。 最后呢，我们来开发一个测试算法的主函数，在内函数当中设置样例中对应的临街矩阵 graph， 顶点零之五 五，分别是北京、天津、郑州、济南、长沙、海南。初始化项链 grove 将全部路径设置为最大值 i， n， f， 并且某个城市至该城市本身的距离是零。 设置图中的各个城市之间的编的值。第一次调用迪杰斯特拉函数计算北京到其他城市的最短距离。第二次调用迪杰斯特拉函数计算郑州到其他城市的最短距离，打印出相关结果。 那么为了更好的测试我们开发的迪杰斯特拉算法代码，我们为大家推荐一个在线测试平台， pog， 北京大学程序设计评测系统。 pog 呢，主要收入的是 acm 国际大学生程序设计竞赛、 noi 青少年信息学、奥林匹克竞赛等各类程序设计竞赛题目，是练习算法的最佳平台。 关于狄吉斯特拉算法呢，有许多相关的题目，小曼今天就通过 pog 幺五零二测试了刚刚讲解的代码， 到这里呢，狄杰斯特拉算法我们就讲完了，下节课我们再会。