最短路径Dijkstra算法

1最短路径两点之间的最短路径问题：求从某个源点到其余各点的最短路径每一对顶点之间的最短路径求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1v2…其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。2Dijkstra算法012345507010353031510152020源点终点路径长度最短路径V0V1（V0，V2，V3，V1）45V2（V0，V2）10V3V4V5（V0，V2，V3）25（V0，V2，V3，V1，V4）55—∞单源最短路径问题是：给定带权的有向图G=（V，E），源点v∈V，求从v到V中其余各顶点的最短路径。如何求解上图中的最短路径问题，Dijkstra提出了一种解决方案。即迪杰斯特拉算法，其基本思想如下：设置辅助数组Dist，其中每个分量Dist[k]表示当前所求得的从源点到其余各顶点k的最短路径的长度。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。INFINITYkvarcsGkDist]][0[.][V0和k之间存在弧V0和k之间不存在弧3）每次从集合V-S中取出具有最短特殊路径长度的顶点u，将u加到S中，同时对数组Dist做必要的修改。若Dist[u]+G.arcs[u][k]Dist[k]则将Dist[k]改为Dist[u]+G.arcs[u][k]。其中，特殊路径指从源点到u中间只经过S中顶点的路径。2）设置一个顶点集合S，存放最短路径的终点。顶点k为当前最短路径的终点,将Vk加入集合S中，而Dist[k]为最短路径的长度。4)重复操作2）、3）共n-1次。由此求得图上其余各顶点的最短路径是依路径长度递增的序列。若带权图G如下所示，根据上述算法来求解源点v0到v2的最短路径。012343530201082541201324330∞∞325884124根据以上分析和举例，不难得出狄杰斯特拉算法，其描述如下：VoidshortestPath(MGraphG,intV0,PathMatrix&P,ShortPathTable&D)//P[v]表示最短路径，D[v]表示带权长度//P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点//final[v]为TRUE，即已经求得从v0到v的最短路径{for（v=0;vG.vexnum;v++）{final[v]=FALSE;D[v]=G.arcs[v0][v];for(w=0;wG.vexnum;w++)P[v][w]=FALSE;//设置空路径if(D[v]INFINTY){P[v][v0]=TRUE;p[v][v]=TRUE;}}D[v0]=0;final[v0]=TRUE;//初始化，v0顶点在S集中//开始主循环，每次求得v0到某个顶点v的最短距离，将v加到S集for(i=1;iG.vexnum;i++){min=INFINITY;for(w=0;wG.vexnum;i++)//求得当前离v0顶点最近距离if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=TRUE;//离v0最近距离顶点v加入S集for(w=0;wG.vexnum;w++)//更新当前最短路径及距离if(!final[w]&&(min+G.arcs[v][w]D[w])){D[w]=min+G.arcs[v][w];P[w]=P[v];P[w][w]=TRUE;}}}