在图的应用中,有一个很重要的需求:我们需要知道从某一个点开始,到其他所有点的最短路径。
这其中,Dijkstra算法是典型的最短路径算法。它的关键思想是以起始点为中心,向外一层层扩散,直到扩展到终点为止。Dijkstra算法能够得出最短路径的最优解,不过它需要遍历计算的节点相当多,所以效率不高。
首先,用最通俗的语言解释。假定有3个顶点,A、B、C,如图:
要求A到其余各点的最短路径。很明显,A到C比A到B更短。有疑惑的是从A->B的最短距离,要么是直接A->B的边,要么是A经过C到B的边更短。我们首先找到最短的边(A->C),然后在此基础上扩展,于其余边去对比找到最小值。顶点再进一步扩充增加,按照这个思想,我们总可以找到A到所有点的最短路径。
算法描述:
从节点1开始到其余各点的dijkstra算法,其中Wa->b表示边a->b的权,d(i)即为最短路径值,顶点集合为V={1,2,3...n}
1.置集合S={1},置顶点集合U={2,3,4...n},数组d(1)=0,d(i)=W1->i(1,i之间存在边)or 无穷大(1,i之间不存在边);
2.在U中,令d(j)=min{d(i),i属于U},将j从U中移至S中,若U为空集则算法结束,否则转3;
3.对全部i属于U,如果存在边j->i,那么置d(i)=min{d(i),
d(j) + Wj->i},转2
Dijkstra算法的思想为;设G=(V,
E)是一个带权有向图,把图中顶点集合V分为两部分,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有源点,以后每求出一条最短路径,就将顶点加入到S中,直到所有顶点都加入到S中,算法结束),第二组为其余未求出最短路径的顶点集合(用U表示),按最短路径的长度次序依次将第二组中的顶点加入到第一组中。
在加入过程中,总保持着从源点v到S中各顶点的最短路径不大于从源点v到U中各顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离即为源点v到该点的最短路径长度。U中顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短距离。
算法具体步骤
1.初始时,S中只有源点,即S
= {v},v的距离为0(到自己的距离为0)。U包含除v外地所有其他顶点,U中顶点u距离为边上的权(若v到u存在边)或
∞ (v到u不存在边,即u不是v的出边邻接点)
2.从U中选取一个距离v最小的顶点k加入到S中(选定的距离就是v到k的最短路径)
3.以k为新考虑的中间点,修改U中各顶点的距离。若从源点v经过顶点k到顶点u的距离比原来距离(不经过顶点k)段,则修改顶点u的距离,修改后的距离值为顶点k的距离加上边k->u的权
4.重复步骤2、3直到所有的顶点都加入到S中
复杂度分析:
实现方式的不同,可能有n次或者n-1次外层的循环,这里取n次。
步骤2每一轮的比较步骤会是n,n-1,n-2...1
步骤3每一轮的更新步骤会是n-1,n-2...1
这样计算出结果大致为 n²
Dijkstra算法的时间复杂度为O(n^2)
空间复杂度取决于存储方式,邻接矩阵为O(n^2)
再看一个例子:
步骤 |
S集合中 |
U集合中 |
1 |
选入A,此时S
此时最短路径A->A 以A为中间点,从A开始找 |
U
A->B
A->C A->U中其他顶点 = ∞
其中A->C |
2 |
选入上一轮中找到的最短路径的顶点C,此时S
此时最短路径A->A 以C为中间点,从A->C=3这条最短路径开始新一轮查找 |
U
A->C->B
替换B的权值为更小的A->C->B
A->C->D
A->C->E A->C->U中其他顶点 = ∞
其中A->C->B |
3 |
选入B,此时S
此时最短路径 A->A
A->C->B
以B为中间点,从A->C->B |
U
A->C->B->D A->C->B->U中其他顶点 = ∞
其中 A->C->D |
4 |
选入D,此时 S
此时最短路径 A->A
以D为中间点,从A->C->D |
U
A->C->D->E
A->C->D->F
其中A->C->E |
5 |
选入E,此时 S
此时最短路径 A->A
以E为中间点,从A->C->E |
U
A->C->E->F
其中A->C->D->F |
6 |
选入F,此时 S
此时最短路径 A->A |
U集合已空,查找完毕 |
算法实现:
伪代码
Dijkstra算法解决了有向图G=(V,
E)上带全的单源最短路径问题,但要求所有的边权非负)。因此,假定每条边(u,v)∈E,有w(u,v)≥0。
Dijksra算法中设置了一个顶点集合S,从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的顶点u∈V-S,并将u加入到S中,对u的所有出边进行松弛。在下面的算法实现中,用到了顶点的最小优先队列Q,排序关键字为顶点的d值。
DIJSTRA(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 S ←
Φ
3 Q ← V[G]
4 while Q≠Φ
5 do u EXTRACT-MIN(Q)
6 S ← S∪{u}
7 for each
vertex v∈Adj[u]
8 do RELAX(u,v,w)