《迪克斯特拉算法》PPT课件

《《迪克斯特拉算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、,v3)50(v0,v4,v3,v5)60迪克斯特拉Dijkstra算法按路径长度递增逐步产生最短路径设集合S存放已经求出的最短路径的终点，开始，S中只有一个源点v0，以后每求得的一条最短路径就将终点加入S，直到全部顶点都加入到S.定义一个数组D[n];n是图的顶点数。D[i]=从源点v0到顶点vi最短路经的长度。第一步取D[i]为v0到vi的边的权值，无边时取值∞，取一个最小值D[j1]=min{D[i],i

3、D[I]10301002D[i]604j2=4D[4]=30是v0到v4的最短路径的长度20L={v0,v2}L={v0,v2,v4}递归过程：重复第二步设已经有v0到vj1,vj2···,vjk的最短路径对每个顶点vi,vi≠vj1,vj2···,vjk,更新D[i]=min{D[i],D[jk]+arc[jk][i]}令D[jk+1]=min{D[i],i

4、2)30(v0,v4)100(v0,v5)2D[i]060(v0,v2,v3)4D[i]50(v0,v4,v3)090(v0,v4,v5)3D[i]060(v0,v4,v3,v5)520迪克斯特拉Dijkstra算法L={v0,v2,v4,v3,v5}时间复杂性O(n2)令L={vj1,vj2···,vjk-1}是已经求得的从v0出发的最短路径的终点的集合，可以证明下一条最短路径(终点vjk),是只通过S中顶点到达vjk的。否则设v0到vjk的路径中有一个不在S中出现的顶点vp，但是路径v0···vp···vjk比v0···v

5、p长应当先有v0···vp的最短路径，以归纳假设vp应当已经出现于L中。templatestructPathInfo{TstartV,endV;intcost;};templateintoperator<=(constPathInfo&a,constPathInfo&b){returna.cost<=b.cost;}//用优先序列实现最短路径算法templateintGraph::MinimumPath(constT&sVertex,constT

6、&eVertex){PQueue>PQ(MaxGraphSize);PathInfopathData;SeqListL,adjL;SeqListIteratoradjLiter(adjL);Tsv,ev;intmincost;pathData.startV=sVertex;pathData.endV=sVertex;pathData.cost=0;PQ.PQInsert(pathData);while(!PQ.PQEmpty()){pathData=PQ.PQDelete(

7、);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.star

8、tV=sv;pathData.endV=ev;pathData.cost=mincost+GetWeight(sv,ev);PQ.PQInsert(pathData);}}}}if(ev==eVertex)returnmincost;elseretur