迪杰斯特拉最短路径

迪杰斯特拉最短路径算法(Dijkstra's shortest path algorithm),由荷兰计算机科学家 艾兹赫尔·迪杰斯特拉 在1956年提出。迪杰斯特拉算法使用了 广度优先搜索 解决赋权有向图的单源最短路径问题

迪杰斯特拉算法 跟 Prim最小生成树 算法特别像,Prim算法 通过当前点到下一个点的权重来决定图走向,而 迪杰斯特拉算法 是通过权重和来决定图走向

该算法常用于路由算法或者作为其他图算法的一个子模块

举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径

还是以下图为例

算法步骤:

1.以某一个点开始,寻找当前该点移动一步可以访问的所有的点(未访问过)

2.计算出所有可能的单条路径的权重和,选择权重最小的路径移动一步,记下移动后的顶点(避免重复访问),同时更新没有访问的点,记录添加的边

3.寻找当前集合可以访问的所有路径,重复2的过程,直到没有新的点可以加入

4.此时由所有边构成的树即为最小生成树。

sv代表选择了的点,sb代表选择了的边,lb代表可以选择的路径
选择顶点0        sv[0] lb[0-1(4),0-7(8)]
选择路径0-1(4)    sv[0,1]  sb[0-1]  lb[0-1-2(12),0-7(8),0-1-7(15)]

选择路径0-7(8)    sv[0,1,7]  sb[0-1,0-7]  lb[0-1-2(12),0-7-8(15),0-7-6(9)]
选择路径0-7-6(9)    sv[0,1,7,6]  sb[0-1,0-7,7-6]  lb[0-1-2(12),0-7-8(15),0-7-6-8(15),0-7-6-5(11)]

选择路径0-7-6-5(11)    sv[0,1,7,6,5]  sb[0-1,0-7,7-6,6-5]  lb[0-1-2(12),0-7-8(15),0-7-6-8(15),0-7-6-5-2(15),
0-7-6-5-3(25),0-7-6-5-4(21)]

选择路径0-1-2(12)  sv[0,1,7,6,5,2]   sb[0-1,0-7,7-6,6-5,1-2]
lb[0-1-2-3(19),0-1-2-8(14),0-7-8(15),0-7-6-8(15),0-7-6-5-3(25),0-7-6-5-4(21)]

选择路径0-1-2-8(14)  sv[0,1,7,6,5,2,8]  sb[0-1,0-7,7-6,6-5,1-2,2-8]
lb[0-1-2-3(19),0-7-6-5-3(25),0-7-6-5-4(21)]

选择路径0-1-2-3(19)  sv[0,1,7,6,5,2,8,3]  sb[0-1,0-7,7-6,6-5,1-2,2-8,2-3]
lb[0-1-2-3-4(28)),0-7-6-5-4(21)]

选择路径0-7-6-5-4(21)  sv[0,1,7,6,5,2,8,3,4]  sb[0-1,0-7,7-6,6-5,1-2,2-8,2-3,5-4]

完成

代码实现请参考:

dijkstras-shortest-path-algorithm

wiki-迪杰斯特拉


上一篇: 哈夫曼编码
下一篇: A*算法-自动寻路
作者邮箱: 203328517@qq.com