Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，读大学时小编也学习过该算法，但理解不是特别透彻，利用这段时间，小编也重新学习了一遍，并把学习过程分享给大家。
一、单源最短路径问题
首先我们在算这个最短路径的时候，针对的是带权有向图，其中每条边的权是非负实数。我们给定一个带权有向图G单源最短路径问题（Single-Source Shortest Paths）。
那为什么要是权值不为负呢，我们举个最简单的反例：
G1
在上图中，顶点V1到V2的路径有两条，V1->V2和V1->V3->V2。第一条路径长度为2，第2条路径长度为1。但实际上第1条路径才是最短的。
二、算法分析
迪杰斯特拉（Dijkstra）算法是一个按照路径长度递增的次序产生最短路径的算法。主要特点是以起始点为中心按照长度递增往外层层扩展（广度优先搜索的思想），直到扩展到终点为止。
1、所需数据结构
我们给定一个有权图G=<V,E>，为了更好的对分析过程进行理解，这里小编把几个需要的辅助数据结构解释一下：
① 顶点集V：图中所有点的集合。
② 点集S：已经找到最短路径的终点集合。
③ 点集U：未计算出最短路径的顶点的集合。
④ 辅助数组Distance【简称D】：D[i]表示当前所找到的从起始点v0【也称源点，自己定义】到每个终点vi的最短路径长度。
D的初态为：若V0到Vi有弧，则D[i]为弧上的权值，否则置D[i]为∞。
⑤ 邻接矩阵arcs：带权有向图。arcs[i][j]表示弧上<Vi，Vj>上的权值。若<Vi，Vj>不存在，则置arcs[i][j]为∞。
⑥ 数组path：起点V0与顶点i的最短路径为V0->...->path[i]->i，即path[i]为该路径中i的前一个结点。
2、从实例来看算法流程
直接上算法流程可能有点难懂，直接从例子入手来看看，以下图G为例：
G
首先初始化下列两个数组：
D[]={∞，∞，∞，∞，∞，∞}【在这里，ABCDEF按照顺序排列（012345）。D[0]表示起点A到自己的路径距离为∞，D[1]表示起点A到顶点B的路径距离为∞，D[2]表示顶点A到顶点C的路径距离为∞，D[3]，D[4]，D[5]同理】。
path[]={-1,-1,-1,-1,-1,-1}。
选取一个起始点【任选】，这里我们选取起始点为A，并设置D[0]=0,
此时D[]={0，∞，∞，∞，∞，∞}；
第一步：选取A，加入集合S。在图G中，有：
S={A}【表示最短路径A->A=0】；
U=V-S={B，C，D，E，F}；
然后以A为中间点，有：
A->B=1，也就是D[0]+arc[0][1]<D[1],对D[1]进行更新，使得D[1]=1,此时path[1]=0【B在顶点集V中下标为1，A为0】；
A->C=12，也就是D[0]+arc[0][2]<D[2],对D[2]进行更新，使得D[2]=12,此时path[2]=0【C在顶点集V中下标为2，A为0】；
A->D=∞，不存在D[0]+arc[0][3]<D[3],因此D[3]以及path[3]都不更新；
A->E=∞，不存在D[0]+arc[0][4]<D[4],因此D[4]以及path[4]都不更新；
A->F=∞，不存在D[0]+arc[0][5]<D[5],因此D[5]以及path[5]都不更新；
此时，D[]={0，1，12，∞，∞，∞},path[]={-1,0,0,-1,-1,-1}。
第二步：选取B，加入S，有：
S={A，B}【最短路径A->A=0,A->B=1】；
U=V-S={C，D，E，F}；
然后以B为中间点，查找发现B->C=9，B->D=3，B->E=∞，B->F=∞。
（A->B+B->C=1+9=10）<(A->C=12),也就是D[1]+arc[1][2]<D[2],对D[2]进行更新，使得D[2]=10,此时path[2]=1【C在顶点集V中下标为2，B为1】；
（A->B+B->D=1+3=4）<(A->D=∞)，也就是D[1]+arc[1][3]<D[3],对D[3]进行更新，使得D[3]=4,此时path[3]=1【D在顶点集V中下标为3，B为1】；
因此：
A->B->C=10
A->B->D=4
A->B->E=∞
A->B->F=∞
对数组D进行更新，得到D[]={0，1，10，4，∞，∞},path[]={-1,0,1,1,-1,-1}
第三步：选入D，加入S，有：
S={A，B，D}【最短路径A->A=0,A->B=1，A->B->D=4】；
U=V-S={C，E，F}；
然后以D为中间点，查找发现D->C=4，D->E=13，D->F=15。
（A->B->D+D->C=4+4=8）<(A->B->C=10),也就是D[3]+arc[3][2]<D[2],对D[2]进行更新，使得D[2]=8,此时path[2]=3【C在顶点集V中下标为2，D为3】；
(A->B->D+D->E=4+13=17）<(A->E=∞),也就是D[3]+arc[3][4]<D[4],对D[4]进行更新，使得D[4]=17,此时path[4]=3【E在顶点集V中下标为4，D为3】；
(A->B->D+D->F=4+15=19）<(A->F=∞),也就是D[3]+arc[3][5]<D[5],对D[4]进行更新，使得D[4]=17,此时path[5]=3【F在顶点集V中下标为5，D为3】；
因此：
A>B->D->C=8
A->B->D->E=17
A->B->D->F=19
对数组D进行更新，得到D[]={0，1，8，4，17，19},path[]={-1,0,3,1,3,3}
第四步：选入C，加入S，有：
S={A，B，D，C}【最短路径A->A=0,A->B=1，A->B->D=4，A->B->D->C=8】；
U=V-S={E，F}；
然后以C为中间点，查找发现C->E=5，C->F=∞。
(A->B->D->C+C->E=8+5=13）<(A->B->D->E=17),也就是D[2]+arc[2][4]<D[4],对D[4]进行更新，使得D[4]=13,此时path[4]=2【E在顶点集V中下标为4，C为2】；
(A->B->D->C+C->F=8+∞=∞）>(A->B->D->F=19),也就是D[2]+arc[2][5]>D[5],D[5]以及path[5]都不进行更新；
因此：
A>B->D->C->E=13
A->B->D->F=19
对数组D进行更新，得到D[]={0，1，8，4，13，19},path[]={-1,0,3,1,2,3}。
第五步：选入E，加入S，有：
S={A，B，D，C，E}【最短路径A->A=0,A->B=1，A->B->D=4，A->B->D->C=8，A>B->D->C->E=13】；
U=V-S={F}；
然后以E为中间点，查找发现E->F=4。
(A->B->D->C->E+E->F=13+4=17）<(A->B->D->F=19),也就是D[4]+arc[4][5]<D[5],对D[5]进行更新，使得D[5]=17,此时path[5]=4【F在顶点集V中下标为5，E为4】；
因此：
A>B->D->C->E->F=17
对数组D进行更新，得到D[]={0，1，8，4，13，17},path[]={-1,0,3,1,2,4}
第六步：选入F，加入S，有：
S={A，B，D，C，E，F}【最短路径A->A=0,A->B=1，A->B->D=4，A->B->D->C=8，A>B->D->C->E=13，A>B->D->C->E->F=17】；
U={}；
此时查找结束。D[]={0，1，8，4，13，17},path[]={-1,0,3,1,2,4}。
通过数组D，就能知道起点A到其他各个顶点的最短路径，分别为0，1，8，4，13，17。
那怎么通过path数组输出最短路径经过的顶点呢？
A到F的路径：path[5]=4，path[4]=2，path[2]=3，path[3]=1，path[1]=0，path[0]=-1，停止。此时A到F的路径【这里为逆序】就为5<-4<-2<-3<-1<-0，也就是F<-E<-C<-D<-<-B<-A。
A到E的路径：path[4]=2，path[2]=3，path[3]=1，path[1]=0，path[0]=-1，停止。此时A到E的路径【这里为逆序】就为4<-2<-3<-1<-0，也就是E<-C<-D<-<-B<-A。
A到D的路径：path[3]=1，path[1]=0，path[0]=-1，停止。此时A到D的路径【这里为逆序】就为3<-1<-0，也就是D<-<-B<-A。
A到C的路径：path[2]=3，path[3]=1，path[1]=0，path[0]=-1，停止。此时A到C的路径【这里为逆序】就为2<-3<-1<-0，也就是C<-D<-<B-<-A。
A到B的路径：path[1]=0，path[0]=-1，停止。此时A到B的路径【这里为逆序】就为1<-0，也就是B<-A。
3、算法流程总结
把上面的流程进行归纳，就是我们课本上经常描述的文字了。
用带权值的邻接矩阵arc来表示带权的有向图，V，S，U，D在前面已经介绍过。
（1）初始化：顶点集S为空，从V0出发到图上其余各顶点Vi可能到达的最短路径长度初值：D[i]=arc[locate(G,V0)][i](Vi ϵ V)， 也就是D[0]=0,其他为+∞。
（2）选择节点Vj，加入集合S,U=V-S,使得：D[j]=Min{D[i]|Vi ϵ U}。其中Vj就是当前求的从v0出发的最短路径的终点
（3）修改从V0出发到集合U上的任一顶点Vk可达的最短路径长度，若：D[j]+arc[j][k]<D[k],则使得D[k]=D[j]+arc[j][k]
（4）重复（2）和（3）,直到U为空。求的V0 到其余顶点的最短路径是依路径长度递增的序列。
三、Dijkstra算法的数学证明
从算法的数学描述可知，只要证明命题“从U中找到D[i]最小的点j，D[j]即为从起点到j的最短路径长度”正确，算法就正确。【i，j为顶点集中的顶点下标】
设置起点为V0，下标为0。
（1）算法找到的第一个点为Vj，下标为j。D[j]即为从起点V0到Vj的最短路径长度。采用反证法：
因为算法找到的第一个点一定是起点V0最近的邻居；
假设D[j]不是从起点到V0的最短路径长度，则存在点Vk，使得|V0->Vk|<|V0->Vj|；
与已知矛盾，故假设不成立，子命题成立。
（2）已用算法从U中依次找到了V1，V2，...Vk共k个点，且D[1],D[2]...D[k]是起点到各顶点的最短路径长度，则此时继续从U中依照算法再找一个点V(k+1)，D[k+1]就是为起点V0到V(k+1)的最短路径长度。
同样采用反证法：
假设D[k+1]不是起点V0到V(k+1)的最短路径长度，所以设置起点到V(k+1)的最短径经过的点的集合为T，路径长度为L，则有L<D[k+1]。
由D[i]的含义可知T∩U不为空集
因为V0ϵT且V0 ϵS，可得到T∩S不为空集
设到V(k+1)的最短路径中，最靠近V(k+1)且不属于S的点为Vx，Vx的后继为Vy；
因为有向图中边均为正权边；
所以有D[x]<D[y]≦L；
又因为Vx不属于S，因此有D[x]>D[k+1]，产生矛盾，故该假设也不成立。
综上所述，该算法是正确的。
四、代码实现
下面是一个邻接矩阵的完整代码，图中就有这个最短路径算法的函数，截图如下所示：
C++算法
有误请指正，谢谢！
网友评论