JOHNSON 全源最短路径算法_第1页
JOHNSON 全源最短路径算法_第2页
JOHNSON 全源最短路径算法_第3页
JOHNSON 全源最短路径算法_第4页
JOHNSON 全源最短路径算法_第5页
已阅读5页,还剩1页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、Johnson全源最短路径算法解决单源最短路径问题(SingleSourceShortestPathsProblem)的算法包括:Dijkstra单源最短路径算法:时间复杂度为O(E+VlogV),要求权值非负;Bellman-Ford单源最短路径算法:时间复杂度为O(VE),适用于带负权值情况;对于全源最短路径问题(All-PairsShortestPathsProblem),可以认为是单源最短路径问题的推广,即分别以每个顶点作为源顶点并求其至其它顶点的最短距离。例如,对每个顶点应用Bellman-Ford算法,则可得到所有顶点间的最短路径的运行时间为O(V2E),由于图中顶点都是连通的,而

2、边的数量可能会比顶点更多,这个时间没有比Floyd-Warshall全源最短路径算法O(V3)更优。那么,再试下对每个顶点应用Dijkstra算法,则可得到所有顶点间的最短路径的运行时间为O(VE+V2logV),看起来优于Floyd-Warshall算法的O(V3),所以看起来使用基于Dijkstra算法的改进方案好像更好,但问题是Dijkstra算法要求图中所有边的权值非负,不适合通用的情况。在1977年,DonaldB.Johnson提出了对所有边的权值进行re-weight的算法,使得边的权值非负,进而可以使用Dijkstra算法进行最短路径的计算。我们先自己思考下如何进行re-wei

3、ght操作,比如,简单地对每条边的权值加上一个较大的正数,使其非负,是否可行?111s-a-b-c/_/4比如上面的图中,共4条边,权值分别为1,1,1,4。当前s-c的最短路径是s-a,a-b,b-c即1+1+1=3。而如果将所有边的权值加1,则最短路径就会变成s-c的5,因为2+2+2=6,实际上导致了最短路径的变化,显然是错误的。那么,Johnson算法是如何对边的权值进行re-weight的呢?以下面的图G为例,有4个顶点和5条边。首先,新增一个源顶点4,并使其与所有顶点连通,新边赋权值为0,如下图所示。使用Bellman-Ford算法计算新的顶点到所有其它顶点的最短路径,则从4至0,

4、1,2,3的最短路径分别是0,-5,-1,0。即有h=0,-5,-1,0。当得到这个h信息后,将新增的顶点4移除,然后使用如下公式对所有边的权值进行re-weight:w(u,v)=w(u,v)+(hu-hv).则可得到下图中的结果:此时,所有边的权值已经被re-weight为非负。此时,就可以利用Dijkstra算法对每个顶点分别进行最短路径的计算了。Johnson算法描述如下:给定图G=(V,E),增加一个新的顶点s,使s指向图G中的所有顶点都建立连接,设新的图为G;对图G中顶点s使用Bellman-Ford算法计算单源最短路径,得到结果h=h0,h1,.hV-1;对原图G中的所有边进行r

5、e-weight,即对于每个边(u,v),其新的权值为w(u,v)+(hu-hv);移除新增的顶点s,对每个顶点运行Dijkstra算法求得最短路径;Johnson算法的运行时间为O(V2logV+VE)。Johnson算法伪码实现如下:Johnson算法C#代码实现如下:复制代码1usingSystem;2usingSystem.Collections.Generic;3usingSystem.Linq;45namespaceGraphAlgorithmTesting67classProgram89staticvoidMain(stringargs)1011/buildadirectedan

6、dnegativeweightedgraph12GraphdirectedGraph1=newGraph(5);13directedGraph1.AddEdge(0,1,-1);14directedGraph1.AddEdge(0,2,4);15directedGraph1.AddEdge(1,2,3);16directedGraph1.AddEdge(1,3,2);17directedGraph1.AddEdge(1,4,2);18directedGraph1.AddEdge(3,2,5);19directedGraph1.AddEdge(3,1,1);2021222324252627282

7、930313233343536373839404142434445464748495051525354555657585960616263directedGraph1.AddEdge(4,3,-3);Console.WriteLine();Console.WriteLine(GraphVertexCount:0,directedGraph1.VertexCount);Console.WriteLine(GraphEdgeCount:0,directedGraph1.EdgeCount);Console.WriteLine();int,distSet1=directedGraph1.Johnso

8、ns();PrintSolution(directedGraph1,distSet1);/buildadirectedandpositiveweightedgraphGraphdirectedGraph2=newGraph(4);directedGraph2.AddEdge(0,1,5);directedGraph2.AddEdge(0,3,10);directedGraph2.AddEdge(1,2,3);directedGraph2.AddEdge(2,3,1);Console.WriteLine();Console.WriteLine(GraphVertexCount:0,directe

9、dGraph2.VertexCount);Console.WriteLine(GraphEdgeCount:0,directedGraph2.EdgeCount);Console.WriteLine();int,distSet2=directedGraph2.Johnsons();PrintSolution(directedGraph2,distSet2);Console.ReadKey();privatestaticvoidPrintSolution(Graphg,int,distSet)Console.Write(t);for(inti=0;ig.VertexCount;i+)Consol

10、e.Write(i+t);Console.WriteLine();Console.Write(t);for(inti=0;ig.VertexCount;i+)Console.Write(-+t);Console.WriteLine();for(inti=0;ig.VertexCount;i+)646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107Console.Write(i+|t);for(intj=0;jg.VertexCount;j+)if(distS

11、eti,j=int.MaxValue)Console.Write(INF+t);elseConsole.Write(distSeti,j+t);Console.WriteLine();classEdgepublicEdge(intbegin,intend,intweight)this.Begin=begin;this.End=end;this.Weight=weight;publicintBeginget;privateset;publicintEndget;privateset;publicintWeightget;privateset;publicvoidReweight(intnewWe

12、ight)this.Weight=newWeight;publicoverridestringToString()returnstring.Format(Begin0,End1,Weight2,Begin,End,Weight);classGraph108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151privateDictionaryint,List_adjacentEdges=new

13、Dictionaryint,List();publicGraph(intvertexCount)this.VertexCount=vertexCount;publicintVertexCountget;privateset;publicintEdgeCountgetreturn_adjacentEdges.Values.SelectMany(e=e).Count();publicvoidAddEdge(intbegin,intend,intweight)if(!_adjacentEdges.ContainsKey(begin)varedges=newList();_adjacentEdges.

14、Add(begin,edges);_adjacentEdgesbegin.Add(newEdge(begin,end,weight);publicvoidAddEdge(Edgeedge)AddEdge(edge.Begin,edge.End,edge.Weight);publicvoidAddEdges(IEnumerableedges)foreach(varedgeinedges)AddEdge(edge);publicIEnumerableGetAllEdges()15215315415515615715815916016116216316416516616716816917017117

15、2173174175176177178179180181182183184185186187188189190191192193194195return_adjacentEdges.Values.SelectMany(e=e);publicint,Johnsons()/distSet,willbetheoutputmatrixthatwillfinallyhavetheshortest/distancesbetweeneverypairofverticesint,distSet=newintVertexCount,VertexCount;for(inti=0;iVertexCount;i+)f

16、or(intj=0;jVertexCount;j+)distSeti,j=int.MaxValue;for(inti=0;iVertexCount;i+)distSeti,i=0;/step1:addnewvertexsandconnecttoallverticesGraphg=newGraph(this.VertexCount+1);g.AddEdges(this.GetAllEdges();ints=this.VertexCount;for(inti=0;ithis.VertexCount;i+)g.AddEdge(s,i,0);/step2:useBellman-Fordtoevalua

17、teshortestpathsfromsinth=g.BellmanFord(s);/step3:re-weightingedgesoftheoriginalgraph/w(u,v)=w(u,v)+(hu-hv)foreach(varedgeinthis.GetAllEdges()edge.Reweight(edge.Weight+(hedge.Begin-hedge.End);/step4:useDijkstraforeachedgesfor(intbegin=0;beginthis.VertexCount;begin+)19619719819920020120220320420520620

18、7208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239intdist=this.Dijkstra(begin);for(intend=0;enddist.Length;end+)if(distend!=int.MaxValue)distSetbegin,end=distend-(hbegin-hend);returndistSet;publicint,FloydWarshell()/*distSet,willbetheoutputmatrixthatwil

19、lfinallyhavetheshortestdistancesbetweeneverypairofvertices*/int,distSet=newintVertexCount,VertexCount;for(inti=0;iVertexCount;i+)for(intj=0;jVertexCount;j+)distSeti,j=int.MaxValue;for(inti=0;ie)distSetedge.Begin,edge.End=edge.Weight;/*Addallverticesonebyonetothesetofintermediatevertices.-Beforestart

20、ofaiteration,wehaveshortestdistancesbetweenallpairsofverticessuchthattheshortestdistancesconsideronlytheverticesinset0,1,2,.k-1asintermediatevertices.-Aftertheendofaiteration,vertexno.kisaddedtothesetof24024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127

21、2273274275276277278279280281282283intermediateverticesandthesetbecomes0,1,2,.k*/for(intk=0;kVertexCount;k+)/Pickallverticesassourceonebyonefor(inti=0;iVertexCount;i+)/Pickallverticesasdestinationfortheabovepickedsourcefor(intj=0;jVertexCount;j+)/Ifvertexkisontheshortestpathfrom/itoj,thenupdatetheval

22、ueofdistSeti,jif(distSeti,k!=int.MaxValue&distSetk,j!=int.MaxValue&distSeti,k+distSetk,jdistSeti,j)distSeti,j=distSeti,k+distSetk,j;returndistSet;publicintBellmanFord(intsource)/distSetiwillholdtheshortestdistancefromsourcetoiintdistSet=newintVertexCount;/Step1:Initializedistancesfromsourcetoallothe

23、rverticesasINFINITEfor(inti=0;iVertexCount;i+)distSeti=int.MaxValue;distSetsource=0;/Step2:Relaxalledges|V|-1times.Asimpleshortestpathfromsource/toanyothervertexcanhaveat-most|V|-1edgesfor(inti=1;ie)intu=edge.Begin;intv=edge.End;28428528628728828929029129229329429529629729829930030130230330430530630

24、7308309310311312313314315316317318319320321322323324325326327intweight=edge.Weight;if(distSetu!=int.MaxValue&distSetu+weighte)intu=edge.Begin;intv=edge.End;intweight=edge.Weight;if(distSetu!=int.MaxValue&distSetu+weightdistSetv)Console.WriteLine(Graphcontainsnegativeweightcycle.);returndistSet;publi

25、cintDijkstra(intsource)/distiwillholdtheshortestdistancefromsourcetoiintdistSet=newintVertexCount;/sptSetiwilltrueifvertexiisincludedinshortest/pathtreeorshortestdistancefromsourcetoiisfinalizedboolsptSet=newboolVertexCount;/initializealldistancesasINFINITEandstpSetasfalsefor(inti=0;iVertexCount;i+)distSeti=int.MaxValue;sptSeti=false;3283293303313323333343353363373383393403

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论