赞
踩
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止(BFS、prime算法都有类似思想)。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
2.算法描述
1)算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤:
a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
执行动画过程如下图
(1)S为已经找到的从v出发的最短路径的终点集合,它的初始状态为空集,那么从v出发到图中其余各顶点(终点)vi(vi∈V-S)可能达到的最短路径长度的初值为:
d[i] = arcs[LocateVex(G, v)][i],vi∈V
(2)选择vj,使得 d[j] = Min{d[i]|vi属于V-S},vj就是当前求得的一条从v出发的最短路径的终点。令S=S∪{j};
(3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果 d[j] + arcs[j][k] < d[k], 则修改d[k]为:d[k] = d[j] + arcs[j][k];
(4)重复(2),知道所有顶点都包含在S中,此时得到v到图上其余各顶点的最短路径是依路径长度递增的序列。
具体图例与算法执行步骤:(从A开始,到各节点的最短路径)
具体执行步骤如下图所示:
PS:图片右下角是原作者的博客地址。
下面是根据路径数组PathMatrix得到具体的路径序列:
以上面的无向网为例,运行结果截图:
dijkstra算法两个应用题:
HDOJ 1874 畅通工程续,现有解法:www.wutianqi.com/?p=1894
HDOJ 2544 最短路,现有解法:www.wutianqi.com/?p=1892
参考:http://hi.baidu.com/zealot886/item/c8a499ee5795bcddeb34c950
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
推荐几篇搜索算法相关的非常好的博文:
一(续)、A*,Dijkstra,BFS算法性能比较及A*算法的应用
二、Dijkstra 算法初探 (Dijkstra算法系列4篇文章)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。