• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    • 查看作者
    • Dijkstra算法求最短路径

      一.  前言

      当我们给定一个有向带权图D与一个点v的时候,点v到D其他顶点的路径可能有多条,那么如何求出点v到D中其他各顶点的最短路径呢?可以用Dijkstra算法解决

      二.  Dijkstra算法

      1.  Dijkstra算法是按照路径长度的递增次序,逐步产生最短路径的算法

      这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时,原点 s 的路径权重被赋为 0 (d[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把d[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于所有顶点的集合 V 中的任意顶点 v, 若 v 不为 s 和上述 m 之一, d[v] = ∞)。当算法结束时,d[v] 中存储的便是从 s 到 v 的最短路径,或者如果路径不存在的话是无穷大。

      2.  边的拓展是Dijkstra 算法的基础操作:如果存在一条从 u 到 v 的边,那么从 s 到 v 的最短路径可以通过将边(u, v)添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小,我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时,每条边(u, v)都只被拓展一次。

      3.  算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ,而集合 Q 则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中,算法对 u 的每条外接边 (u, v) 进行拓展。

      三.  举例

      以下图为例:

      Dijkstra算法求最短路径

      我们可以构建数组,来更好的分析Dijkstra算法:

      最短路径就是起始顶点到该节点的最短路径长度(权值)

      上一个顶点就是起始顶点到该顶点的最短路径的前一个顶点,如果没有设置为-1

      设顶点被使用状态为1,未被使用状态为0

      Dijkstra算法求最短路径

      1.  首先从顶点0开始:

      0到自身权值为0,同时顶点0为起始顶点,所以将0顶点的上一个顶点设为-1

      0顶点到1的权值为10,同时,顶点1的上一个顶点设置为0

      0顶点到2的权值没有直达边,所以用无穷表示,同时,顶点2的上一个顶点设置为-1

      0顶点到3的权值为30,同时,顶点3的上一个顶点设置为0

      0顶点到4的权值为100,同时,顶点4的上一个顶点设置为0

      使用完顶点0,将顶点0是否被使用设置为1,如下图:

      Dijkstra算法求最短路径

      2.  顶点0已经被使用,接下来从未被使用的顶点中选取从顶点0到该顶点权值最小的顶点1开始,1到2的权值为50,而0可以从1到2,则0到2这条路径的权值为10 + 50 = 60,60 < 无穷,所以将2的最短路径更新为60,同时顶点2上一个顶点更新为1,使用完1顶点,更新使用状态为1

      Dijkstra算法求最短路径

      3.  接下来,从未被使用的顶点有2,3,4,其中0到3的权值最小,为30,而3到2的权值是20,而0可以从3到2,则0到2这条路径的权值为30 + 20 = 50, 50 < 60,将顶点2的最短路径更新为50,同时上一个顶点更新为3

      Dijkstra算法求最短路径

      4.  顶点3还可以到4,到4为权值为60,而0可以从3到4,则0到4这条路径的权值为30 + 60 = 90, 90 < 100, 则将顶点4的最短路径更新为90,同时上一个顶点更新为3,顶点3使用完毕,更新使用状态为1

      Dijkstra算法求最短路径

      5.  接下来,从未被使用的顶点有2,4,其中0到2的权值最小,为30,2到4权值为10,而0可以从3到2再到4,则这条路径的权值为:30 + 20 + 10 = 60 , 60 < 90 ,则将顶点4的最短路径更新为60,同时上一个顶点更新为2,顶点2使用完毕,更新使用状态为1

      Dijkstra算法求最短路径

      6.  还剩最后一个顶点4,但是顶点4出度为0,算法完成,则

      0到1最短路径:10

      0到2最短路径:50

      0到3最短路径:30

      0到4最短路径:60

      7.  我们知道了起始顶点到每一个顶点的最短距离,那么如何根据上面的数组,将起始顶点到每个顶点的最短距离的路径还原出来呢?以顶点4为例,步骤如下:

      通过上图我们可以看出,顶点4的上一个顶点为2,顶点2的上一个顶点为3,顶点3的上一个顶点为0,则

      0到4的最短路径为:0 —> 3 —> 2 —> 4,依次类推

      0到3的最短路径为:0 —> 3

      0到2的最短路径为:0 —> 3 —> 2

      0到1的最短路径为:0 —> 1

      四.  参考资料

      《数据结构》殷人昆版

      维基百科戴克斯特拉算法

    • 0
    • 0
    • 0
    • 3.2k
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: