迪克斯特拉算法PPT课件

1、2021/3/91电子系2000级数据结构 Data Structure With C or C+2021/3/92最短路径两点间边数最少的路径 可用作交通自动咨询系统两点间边权重的和最小的路径 用来计算两城市间路程最短， 时间最快，费用最省的路径 2021/3/93两点A,B之间边数最少的路径从A点出发，对图做广度优先遍历。从根A到B的路径就是边数最少的路径，也就是中转次数最少的路径。2021/3/94单源点到其余各点权重和最小的路径 从v0到其余各点的最短路径v3v0v5v2v450v153060100201010 起点 终点 最短路径长度 v0 v1 v2 v3 v4 v5 (v0,v4

2、) 30(v0,v2) 10 (v0,v4,v3) 50(v0,v4,v3,v5) 60 2021/3/95 迪克斯特拉Dijkstra算法按路径长度递增逐步产生最短路径设集合S存放已经求出的最短路径的终点，开始，S中只有一个源点v0，以后每求得的一条最短路径就将终点加入S，直到全部顶点都加入到S.定义一个数组 Dn; n是图的顶点数。Di=从源点v0到顶点vi最短路经的长度。第一步 取Di为v0到vi的边的权值，无边时取值，取一个最小值 Dj1=minDi, in Dj1是v0到vj1的最短路径的长度。 2021/3/96第一步v3v0v5v2v450v1530601001010 1 2 3

3、 4 5 6Di 10 30 100j1=2D2=10是v0到v2的最短路径的长度20L=v0L=v0,v22021/3/97迪克斯特拉Dijkstra算法 已经有L=v0,v2 ，下一条最短路径(终点vj2),或者是(v0 vj2), 或者是(v0, vj1,vj2) 。 对每个顶点vi, 比较Di与Dj1+arcj1i, 取其小 更新 Di=minDi, Dj1+arcj1i 取 Dj2=minDi, in,ij1 则 Dj2是v0到vj2的最短路径的长度。 2021/3/98第二步v3v0v5v2v450v1530601001010 1 2 3 4 5 6 jDI 10 30 100 2

4、Di 60 4j2=4D4=30是v0到v4的最短路径的长度20L=v0,v2L=v0,v2,v42021/3/99递归过程：重复第二步设已经有v0到vj1 ,vj2,vjk的最短路径 对每个顶点vi, vi vj1 ,vj2,vjk, 更新 Di=minDi, Djk+arcjki 令 Djk+1=minDi, in,i j1 ,j2,jk 则 Djk+1是v0到vjk+1的最短路径的长. 2021/3/910v3v0v5v2v450v1530601001010 1 2 3 4 5 LDi 0 10(v0,v2) 30(v0,v4) 100 (v0,v5) 2Di 0 60 (v0,v2,v

5、3) 4Di 50(v0,v4,v3) 0 90 (v0,v4,v5) 3Di 0 60 (v0,v4,v3,v5) 520迪克斯特拉Dijkstra算法L=v0,v2,v4,v3,v5时间复杂性O(n2)2021/3/911 令L=vj1 ,vj2,vjk-1是已经求得的从v0出发的最短路径的终点的集合，可以证明下一条最短路径(终点vjk),是只通过S中顶点到达vjk的 。 否则设v0到vjk的路径中有一个不在S中出现的顶点vp，但是路径v0vpvjk比v0vp长 应当先有v0vp的最短路径，以归纳假设vp应当已经出现于L中。 2021/3/912template struct PathIn

6、fo T startV, endV; int cost; template int operator = (const PathInfo& a, const PathInfo& b) return a.cost = b.cost;2021/3/913/用优先序列实现最短路径算法template int Graph:MinimumPath(const T & sVertex, const T & eVertex) PQueue PathInfo PQ(MaxGraphSize); PathInfo pathData; SeqList L, adjL; SeqListIterator adjLit

7、er(adjL); T sv, ev; int mincost; 2021/3/914 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

8、; adjL = GetNeighbors(sv); adjLiter.SetList(adjL); 2021/3/915for(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

9、 mincost; else return -1;2021/3/916templateT GetVertex(Graph G,int pos) int i, n=G.NumberOfVertices( ); if(pos=n) cerrThere are not so many vertices!; return 0; VertexIterator liter(G); i = 0; while(!liter.EndOfList( ) & i != pos) i+; liter.Next( ); return liter.Data( );2021/3/917templatevoid Shorte

10、stPathDijkstra(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;in;i+) finali=0; v=GetVertex(G,i); for(j=0;jn;j+)Pij=0;/initial Pij Di=G.GetWeight(u,v); /initial Di if(DiMaxInt) Piv0=1;Pii=1; / pij=1 iff vertex j is in

11、 the path from v0 to i 2021/3/918 Dv0=0; finalv0=1; for(i=1;in;i+) min=MaxInt; for(j=1;jn;j+) /Get the minimum Dk if(finalj=0) /vertex j has not marked. if(Djmin) k=j; min=Dj; finalk=1; /marked vertex k, v=GetVertex(G,k); /found the shortest path for(j=1;jn;j+) w=GetVertex(G,j); l=G.GetWeight(v,w)+m

12、in;if(!finalj&(lDw) Dw=l; /renew Dw Pj=Pk; Pjj=1; 2021/3/919void 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;in;i+) coutPi= ; coutPi0; for(int j=1;jn;j+) cout,Pij; coutendl; 2021/3/920每一对顶点之间的

13、最短路径可让每个顶点作起始点以用Dijkstra算法算一遍，共n遍，时间复杂性O(n3).弗洛伊德Floyd算法更直接2021/3/921弗洛伊德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不变。2021/3/922v0v23v124611 D D-1 D0 D1 D2 0 1 2 0 1 2 0 1 2 0 1 2 0

14、0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 0 3 7 0 3 7 0 3 7 0 P P-1 P0 P1 P2 0 1 2 0 1 2 0 1 2 0 1 2 0v0v1v0v2v0v1v0v2v0v1v0v1v2v0v1v0v1v2 1v1v0v1v2v1v0v1v2v1v0v1v2v1v2v0v1v2 2v2v0v2v0v2v0v1v2v0v2v0v1v2v0v2v0v12021/3/923弗洛伊德Floyd算法int *D=new (int*n)n;int *P= new (int*n)n)n;D-1ij=arcij;

15、Dkij=minDk-1ij, Dk-1ik+ Dk-1kj2021/3/924#includegraph.h#define MaxInt 32767typedef int* DistanceMatrix;typedef int* PathMatrix;2021/3/925template void ShortestPathFloyd( Graph G,PathMatrix *&P, DistanceMatrix& D) int n=G.NumberOfVertices( ); int i,j,k,l,t; T u,v,w; for(i=0;in;i+) u=GetVertex(G,i); for(j=0;j0)Dij=l; for(k=0;kn;k+) Pijk=0; if(DijMaxInt) Piji=1;Pijj=1; 2021/3/926for(k=0;kn;k+)for(i=0;in;i+) for(j=0;jn;j+) if(Dik+DkjDij) Dij=Dik+Dkj; for(t=0;tn;t+) Pijt=Pikt|Pkjt; 2021/3/927void main( ) Graph G; G.ReadGraph(sctest.dat