1.解决的问题
求解单源最短路径,但不适用于有负权值的带权图。
2.算法思想
- 集合T中存放已求得最短路径的顶点;
- 集合U中存放待求最短路径的顶点;
- 每次从集合U中取出一个起始点Vs(源点)到其路径长度最小的一个顶点Vr加入到集合T中;
- 更新Vr所有邻接顶点Vk到Vs的路径长度;
- 重复
2,3
步骤,直到集合U为空。
3.伪代码
将源点Vs加入到集合T; // T的初始化 将源点Vs到各个顶点Vj的路径长度初始化为无穷大; while U不为空 { 从U中取距离源点Vs路径最短的顶点Vr加入集合T; 获得Vs到Vr的路径Vs->...->Vr及其路径长度,该路径为Vs到Vr的最短路径; 获取Vr的每个邻接顶点Vk,更新Vs到Vk的路径,操作如下: if (Vs到Vr的路径长度 Dsr+d<r,k> 小于 Dsk) { // 更新Vs到Vk的路径长度 Dsk = Dsr+d<r,k>; } 从U中删除顶点Vr; }
4.手算示例
对图G进行顶点3到其余顶点的最短路径

初始化:将源点3加入到集合T中,其他顶点加入集合U中
路径终点 | 初始化 | 第一趟 | 第二趟 | 第三趟 | 第四趟 | 第五趟 |
1 | 7 3→1 | 7 3→1 | 7 3→1 | |||
2 | ∞ | ∞ | 10 3→5→2 | 10 3→5→2 | ||
3 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | ∞ | ∞ | ∞ | 47 3→1→4 | 22 3→5→2→4 | 22 3→5→2→4 |
5 | 6 3→5 | 6 3→5 | ||||
6 | ∞ | ∞ | 14 3→5→6 | 14 3→5→6 | 14 3→5→6 | |
选择的顶点 | 3 | 5 | 1 | 2 | 6 | 4 |
T | {3} | {3,5} | {3,5,1} | {3,5,1,2} | {3,5,1,2,6} | {3,5,1,2,6,4} |
U | {1,2,4,5,6} | {1,2,4,6} | {2,4,6} | {4,6} | {4} | {} |