JOHNSON 全源最短路径算法

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