Dijkstra

9.3Dijkstra算法第六小组:荣宁贪婪算法的应用之一即单起点最段路径问题abcde5463ae2db74243例如:找出从a到e的最短路径：从a到e的最短路径为：a-b-d-e路径长度=3+2+4=9两点之间的最短路径问题求从某个源点到其余各点的最短路径每一对顶点之间的最短路径求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。v2在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：路径长度最短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。其余最短路径的特点：再下一条路径长度次短的最短路径的特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。求最短路径的迪杰斯特拉算法：一般情况下，Dist[k]=源点到顶点k的弧上的权值或者=源点到其它顶点的路径长度+其它顶点到顶点k的弧上的权值。设置辅助数组Dist，其中每个分量Dist[k]表示当前所求得的从源点到其余各顶点k的最短路径。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][k]Dist[k]则将Dist[k]改为Dist[u]+G.arcs[u][k]。INFINITYkvarcsGkDist]][0[.][V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。迪杰斯特拉算:voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){intfinal[NumVertices];intw;for(intv=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]INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}for(inti=1;iG.vexnum;++i){intmin=INFINITY;for(w=0;wG.vexnum;++w)if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=TRUE;for(w=0;wG.vexnum;++w)if(!final[w]&&(min+G.arcs[v][w]D[w])){D[w]=min+G.arcs[v][w];for(intj=0;jG.vexnum;++j)P[w][j]=P[v][j];P[w][w]=TRUE;}}}算法的时间复杂度：O(n2)(1)初始化：S←{v0};D[j]←arcs[0][j],j=1,2,…,n-1;//n为图中顶点个数(2)求出最短路径的长度：D[k]←min{D[i]},iV-S;S←SU{k};(3)修改：D[i]←min{D[i],D[k]+arcs[k][i]},对于每一个iV-S;(4)判断：若S=V,则算法结束，否则转(2)Dijkstra算法可描述如下:求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。若vi,vj存在，则存在路径{vi,vj}//路径中不含其它顶点若vi,v1,v1,vj存在，则存在路径{vi,v1,vj}//路径中所含顶点序号不大于1若{vi,…,v2},{v2,…,vj}存在，则存在一条路径{vi,…,v2,…vj}//路径中所含顶点序号不大于2…依次类推，则vi至vj的最短路径应是上述这些路径中，路径长度最小者。鸣谢：第六小组全体成员计算机光测量研究所