最短路径(Dijkstra)算法

一、算法功能

给定一个出发点(单源点)和一个有向网G=(V, E), 求出源点到其它各顶点之间的最短路径。

二、算法思想

(1)把图中顶点集合分成两组,第一组为集合S,存放已求出其最短路径的顶点,第二组为尚未确定最短路径的顶点集合是V-S(令W=V-S),其中V为网中所有顶点集合。

(2)按最短路径长度递增的顺序逐个把W中的顶点加到S中,直到S中包含全部顶点,而W为空。

(3)在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到W中任何顶点的最短路径长度。

(4)此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,W中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。