算法流程
我们定义带权图 G 所有顶点的集合为 V，接着我们再定义已确定从源点出发的
最短路径的顶点集合为U，初始集合U为空，记从源点s出发到每个顶点v的距离
为 dis t
v
，初始dist
s
=0。接着执行以下操作：
1. 从V−U 中找出一个距离源点最近的顶点 v，将v加入集合U，并用dist
v
和
顶点v连出的边来更新和v相邻的、不在集合U中的顶点的dist；
2. 重复第一步操作，直到V=U 或找不出一个从s出发有路径到达的顶点，算
法结束。
如果最后V≠U，说明有顶点无法从源点到达；否则每个dist
i
表示从s出发到顶点
i 的最短距离。
评论0