迪克斯特拉算法.ppt

电子系2000级数据结构 Data Structure With C or C+,最短路径,两点间边数最少的路径 可用作交通自动咨询系统 两点间边权重的和最小的路径 用来计算两城市间路程最短， 时间最快，费用最省的路径,两点A,B之间边数最少的路径,从A点出发，对图做广度优先遍历。 从根A到B的路径就是边数最少的路径，也就是中转次数最少的路径。,单源点到其余各点权重和最小的路径,从v0到其余各点的最短路径,v3,v0,v5,v2,v4,50,v1,5,30,60,100,20,10,10,(v0,v4) 30,(v0,v2) 10,(v0,v4,v3) 50,(v0,v4,v3,v5) 60,迪克斯特拉Dijkstra算法,按路径长度递增逐步产生最短路径 设集合S存放已经求出的最短路径的终点，开始，S中只有一个源点v0，以后每求得的一条最短路径就将终点加入S，直到全部顶点都加入到S. 定义一个数组 Dn; n是图的顶点数。 Di=从源点v0到顶点vi最短路经的长度。 第一步 取Di为v0到vi的边的权值，无边时取值， 取一个最小值 Dj1=minDi, i<n Dj1是v0到vj1的最短路径的长度。,第一步,v3,v0,v5,v2,v4,50,v1,5,30,60,100,10,10,j1=2 D2=10 是v0到v2的最短路径的长度,20,L=v0,L=v0,v2,迪克斯特拉Dijkstra算法,已经有L=v0,v2 ，下一条最短路径(终点vj2),或者是(v0 vj2), 或者是(v0, vj1,vj2) 。 对每个顶点vi, 比较Di与Dj1+arcj1i, 取其小 更新 Di=minDi, Dj1+arcj1i 取 Dj2=minDi, i<n,ij1 则 Dj2是v0到vj2的最短路径的长度。,第二步,v3,v0,v5,v2,v4,50,v1,5,30,60,100,10,10,j2=4 D4=30 是v0到v4的最短路径的长度,20,L=v0,v2,L=v0,v2,v4,递归过程：重复第二步,设已经有v0到vj1 ,vj2,vjk的最短路径 对每个顶点vi, vi vj1 ,vj2,vjk, 更新 Di=minDi, Djk+arcjki 令 Djk+1=minDi, i<n,i j1 ,j2,jk 则 Djk+1是v0到vjk+1的最短路径的长.,v3,v0,v5,v2,v4,50,v1,5,30,60,100,10,10,20,迪克斯特拉Dijkstra算法,L=v0,v2,v4,v3,v5,时间复杂性O(n2),令L=vj1 ,vj2,vjk-1是已经求得的从v0出发的最短路径的终点的集合，可以证明下一条最短路径(终点vjk),是只通过S中顶点到达vjk的 。 否则设v0到vjk的路径中有一个不在S中出现的顶点vp，但是路径v0vpvjk比v0vp长 应当先有v0vp的最短路径，以归纳假设vp应当已经出现于L中。,template struct PathInfo T startV, endV; int cost;,template int operator ,/用优先序列实现最短路径算法template int Graph:MinimumPath(const T ,pathData.startV = sVertex; pathData.endV = sVertex; pathData.cost = 0; PQ.PQInsert(pathData); while (!PQ.PQEmpty( ) pathData = PQ.PQDelete( ); ev = pathData.endV; mincost = pathData.cost; if (ev = eVertex) break; if (!FindVertex(L,ev) L.Insert(ev); sv = ev; adjL = GetNeighbors(sv); adjLiter.SetList(adjL);,for(adjLiter.Reset( );!adjLiter.EndOfList( ); adjLiter.Next( ) ev = adjLiter.Data( ); if (!FindVertex(L,ev) pathData.startV = sv; pathData.endV = ev; pathData.cost = mincost+GetWeight(sv,ev); PQ.PQInsert(pathData); if (ev = eVertex) return mincost; else return -1;,templateT GetVertex(Graph G,int pos) int i, n=G.NumberOfVertices( ); if(pos=n) cerr liter(G); i = 0; while(!liter.EndOfList( ) ,templatevoid ShortestPathDijkstra(Graph G, int v0,int *D,int*P) int i, j,k,l,min, n=G.NumberOfVertices( ); T u,v,w; u=GetVertex(G,v0); int *final=new intn; for( i=0;i<n;i+) finali=0; v=GetVertex(G,i); for(j=0;j<n;j+)Pij=0;/initial Pij Di=G.GetWeight(u,v); /initial Di if(Di<MaxInt) Piv0=1;Pii=1; / pij=1 iff vertex j is in the path from v0 to i ,Dv0=0; finalv0=1; for(i=1;i<n;i+) min=MaxInt; for(j=1;j<n;j+) /Get the minimum Dk if(finalj=0) /vertex j has not marked. if(Dj<min) k=j; min=Dj; finalk=1; /marked vertex k, v=GetVertex(G,k); /found the shortest path for(j=1;j<n;j+) w=GetVertex(G,j); l=G.GetWeight(v,w)+min;if(!finalj ,void main( ) Graph G; G.ReadGraph(sctest.dat); int n=G.NumberOfVertices( ); int *D=new intn; int *P=new (int*n)n; ShortestPathDijkstra(G,0,D,P); for(int i=0;i<n;i+) cout<<P<<i<<= ; cout<<Pi0; for(int j=1;j<n;j+) cout<<,<<Pij; cout<<<<endl; ,每一对顶点之间的最短路径,可让每个顶点作起始点以用Dijkstra算法算一遍，共n遍，时间复杂性O(n3). 弗洛伊德Floyd算法更直接,弗洛伊德Floyd算法,定义Dk(u,v)为从u到v的长度最短的k-path. 假设已知从u到v的最短(k-1)-path，则最短k-path要么经过，要么不经过顶点k。如果经过顶点k,则最短k-path是从u到k的最短(k-1)-path,再连接从k到v的最短(k-1)-path。如果不经过顶点k，则最短路径保持k-1-path不变。,v0,v2,3,v1,2,4,6,11,弗洛伊德Floyd算法,int *D=new (int*n)n; int *P= new (int*n)n)n; D-1ij=arcij; Dkij=minDk-1ij, Dk-1ik+ Dk-1kj,#includegraph.h#define MaxInt 32767typedef int* DistanceMatrix;typedef int* PathMatrix;,template void ShortestPathFloyd( Graph G,PathMatrix * ,for(k=0;k<n;k+)for(i=0;i<n;i+) for(j=0;j<n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; for(t=0;t<n;t+) Pijt=Pikt|Pkjt; ,void main( ) Graph G; G.ReadGraph(sctest.dat); int n=G.NumberOfVertices( ); DistanceMatrix D=new (int* n)n; PathMatrix* P=new (int*)n; for(int i=0;i<n;i+) Pi=new (int* n)n; ShortestPathFloyd(G,P,D); for( i=0;i<n;i+) cout<<endl; for(int j=0;j<n;j+) cout<<Dij<< ; ,