dijkstra迪杰斯特拉算法
原文:http://www.cnblogs.com/sadgeminids/archive/2011/12/29/2306719.html
在图的应用中,有一个很重要的需求:我们需要知道从某一个点开始,到其他所有点的最短路径。
这其中,Dijkstra算法是典型的最短路径算法。它的关键思想是以起始点为中心,向外一层层扩散,直到扩展到终点为止。Dijkstra算法能够得出最短路径的最优解,不过它需要遍历计算的节点相当多,所以效率不高。
首先,用最通俗的语言解释。假定有3个顶点,A、B、C,如图:
要求A到其余各点的最短路径。很明显,A到C比A到B更短。有疑惑的是从A->B的最短距离,要么是直接A->B的边,要么是A经过C到B的边更短。我们首先找到最短的边(A->C),然后在此基础上扩展,于其余边去对比找到最小值。顶点再进一步扩充增加,按照这个思想,我们总可以找到A到所有点的最短路径。
算法具体步骤
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中
再看一个例子:
步骤 |
S集合中 |
U集合中 |
1 |
选入A,此时S ={A} 此时最短路径A->A = 0 以A为中间点,从A开始找 |
U = {B, C, D, E, F} A->B = 6 A->C = 3 A->U中其他顶点 = ∞ 其中A->C = 3 权值为最小,路径最短 |
2 |
选入上一轮中找到的最短路径的顶点C,此时S = {A, C} 此时最短路径A->A = 0,A->C = 3 以C为中间点,从A->C=3这条最短路径开始新一轮查找 |
U = {B, D, E, F} A->C->B = 5(比上面的A->B = 6要小) 替换B的权值为更小的A->C->B = 5 A->C->D = 6 A->C->E = 7 A->C->U中其他顶点 = ∞ 其中A->C->B = 5 最短 |
3 |
选入B,此时S = {A, C, B} 此时最短路径 A->A = 0,A->C = 3 A->C->B = 5 以B为中间点,从A->C->B = 5这条最短路径开始新一轮查找 |
U = {D, E, F} A->C->B->D = 10(比上面的A->C->D = 6大,不替换,保持D的权值为A->C->D=6) A->C->B->U中其他顶点 = ∞ 其中 A->C->D = 6 最短 |
4 |
选入D,此时 S = {A, C, B, D} 此时最短路径 A->A = 0,A->C = 3,A->C->B = 5,A->C->D = 6 以D为中间点,从A->C->D = 6这条最短路径开始新一轮查找 |
U = {E, F} A->C->D->E = 8(比上面步骤2中的A->C->E = 7要长,保持E的权值为A->C->E =7) A->C->D->F = 9 其中A->C->E = 7最短 |
5 |
选入E,此时 S = {A, C, B, D ,E} 此时最短路径 A->A = 0,A->C = 3,A->C->B = 5,A->C->D = 6,A->C->E =7, 以E为中间点,从A->C->E = 7这条最短路径开始新一轮查找 |
U = {F} A->C->E->F = 12(比第4步中的A->C->D->F = 9要长,保持F的权值为A->C->D->F = 9) 其中A->C->D->F =9最短 |
6 |
选入F,此时 S = {A, C, B, D ,E, F} 此时最短路径 A->A = 0,A->C = 3,A->C->B = 5,A->C->D = 6,A->C->E =7,A->C->D->F = 9 |
U集合已空,查找完毕 |