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

下载文档

26
0
约4.08千字
约 27页
2018-06-20 发布于北京
举报
版权申诉
保障服务

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

1、本文档共27页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

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

电子系2000级数据结构 Data Structure With C or C++;最短路径;两点A,B之间边数最少的路径;单源点到其余各点权重和最小的路径; 迪克斯特拉Dijkstra算法;第二步;递归过程：重复第二步;v3; ;template class T struct PathInfo{ T startV, endV; int cost;}; ;//用优先序列实现最短路径算法template class T int Graph T ::MinimumPath(const T sVertex, const T eVertex){ PQueue PathInfo T PQ(MaxGraphSize); PathInfo T pathData; SeqList T L, adjL; SeqListIterator T adjLiter(adjL); T sv, ev; int mincost; ; 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;};templateclass TT GetVertex(GraphT G,int pos){ int i, n=G.NumberOfVertices( ); if(pos0||pos=n) {cerrThere are not so many vertices!; return 0; } VertexIteratorT liter(G); i = 0; while(!liter.EndOfList( ) i != pos) { i++; liter.Next( ); } return liter.Data( );};templateclass Tvoid ShortestPathDijkstra(GraphT 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 int[n]; for( i=0;in;i++) { final[i]=0; v=GetVertex(G,i); for(j=0;jn;j++)P[i][j]=0;//initial P[i][j] D[i]=G.GetWeight(u,v); //initial D[i] if(D[i]MaxInt){ P[i][v0]=1;P[i][i]=1;}