|
071 路线规划(四):最短路径之Dijkstra算法
从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。Dijkstra算法(迪杰斯特拉算法),应用了贪心算法模式,是目前公认的最好的求解最短路径的方法。
算法的步骤如下:
先生成两个集合,其中遍历过的节点集合为S,集合U中则为其余节点,即未遍历过的节点。
1、初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则{u,v}正常有权值,若u不是v的出边邻接点,则{u,v}权值为∞。
2、从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是v到k的最短路径长度)。
3、以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值为顶点k的距离加上边上的权。
4、重复步骤2和3,直到所有顶点都包含在S中。
举例如下,寻找从A到F的最短路径,其中线上的数字是两地间的距离。
|
|