Johnson全源最短路径算法
解决单源最短路径问题（SingleSourceShortestPathsProblem）的算法包括：
Dijkstra单源最短路径算法：时间复杂度为O(E+VlogV)，要求权值非负；
Bellman-Ford单源最短路径算法：时间复杂度为O(VE)，适用于带负权值情况；
对于全源最短路径问题（All-PairsShortestPathsProblem），可以认为是单源最短路径问题的推广，即分别以每个顶点作为源顶点并求其至其它顶点的最短距离。例如，对每个顶点应用Bellman-Ford算法，则可得到所有顶点间的最短路径的运行时间为O(V2E)，由于图中顶点都是连通的，而边的数量可能会比顶点更多，这个时间没有比Floyd-Warshall全源最短路径算法O(V3)更优。那么，再试下对每个顶点应用Dijkstra算法，则可得到所有顶点间的最短路径的运行时间为O(VE+V2logV)，看起来优于Floyd-Warshall算法的O(V3)，所以看起来使用基于Dijkstra算法的改进方案好像更好，但问题是Dijkstra算法要求图中所有边的权值非负，不适合通用的情况。
在1977年，DonaldB.Johnson提出了对所有边的权值进行"re-weight"的算法，使得边的权值非负，进而可以使用Dijkstra算法进行最短路径的计算。
我们先自己思考下如何进行"re-weight"操作，比如，简单地对每条边的权值加上一个较大的正数，使其非负，是否可行？
111
s-----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,1,2,3}的最短路径分别是{0,-5,-1,0}。即有h[]={0,-5,-1,0}。当得到这个h[]信息后，将新增的顶点4移除，然后使用如下公式对所有边的权值进行"re-weight"：
w(u,v)=w(u,v)+(h[u]-h[v]).
则可得到下图中的结果：
此时，所有边的权值已经被"re-weight"为非负。此时，就可以利用Dijkstra算法对每个顶点分别进行最短路径的计算了。
Johnson算法描述如下：
给定图G=(V,E)，增加一个新的顶点s，使s指向图G中的所有顶点都建立连接，设新的图为G’；
对图G’中顶点s使用Bellman-Ford算法计算单源最短路径，得到结果h[]={h[0],h[1],..h[V-1]}；
对原图G中的所有边进行"re-weight"，即对于每个边(u,v)，其新的权值为w(u,v)+(h[u]-h[v])；
移除新增的顶点s，对每个顶点运行Dijkstra算法求得最短路径；
Johnson算法的运行时间为O(V2logV+VE)。
Johnson算法伪码实现如下：
Johnson算法C#代码实现如下：
复制代码
1usingSystem;
2usingSystem.Collections.Generic;
3usingSystem.Linq;
4
5namespaceGraphAlgorithmTesting
6{
7classProgram
8{
9staticvoidMain(string[]args)
10{
11//buildadirectedandnegativeweightedgraph
12GraphdirectedGraph1=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);
20directedGraph1.AddEdge(4,3,-3);
21
22Console.WriteLine();
23Console.WriteLine("GraphVertexCount:{0}",directedGraph1.VertexCount);
24Console.WriteLine("GraphEdgeCount:{0}",directedGraph1.EdgeCount);
25Console.WriteLine();
26
27int[,]distSet1=directedGraph1.Johnsons();
28PrintSolution(directedGraph1,distSet1);
29
30//buildadirectedandpositiveweightedgraph
31GraphdirectedGraph2=newGraph(4);
32directedGraph2.AddEdge(0,1,5);
33directedGraph2.AddEdge(0,3,10);
34directedGraph2.AddEdge(1,2,3);
35directedGraph2.AddEdge(2,3,1);
36
37Console.WriteLine();
38Console.WriteLine("GraphVertexCount:{0}",directedGraph2.VertexCount);
39Console.WriteLine("GraphEdgeCount:{0}",directedGraph2.EdgeCount);
40Console.WriteLine();
41
42int[,]distSet2=directedGraph2.Johnsons();
43PrintSolution(directedGraph2,distSet2);
44
45Console.ReadKey();
46}
47
48privatestaticvoidPrintSolution(Graphg,int[,]distSet)
49{
50Console.Write("\t");
51for(inti=0;i
52{
53Console.Write(i+"\t");
54}
55Console.WriteLine();
56Console.Write("\t");
57for(inti=0;i
58{
59Console.Write("-"+"\t");
60}
61Console.WriteLine();
62for(inti=0;i
63{
64Console.Write(i+"|\t");
65for(intj=0;j
66{
67if(distSet[i,j]==int.MaxValue)
68{
69Console.Write("INF"+"\t");
70}
71else
72{
73Console.Write(distSet[i,j]+"\t");
74}
75}
76Console.WriteLine();
77}
78}
79
80classEdge
81{
82publicEdge(intbegin,intend,intweight)
83{
84this.Begin=begin;
85this.End=end;
86this.Weight=weight;
87}
88
89publicintBegin{get;privateset;}
90publicintEnd{get;privateset;}
91publicintWeight{get;privateset;}
92
93publicvoidReweight(intnewWeight)
94{
95this.Weight=newWeight;
96}
97
98publicoverridestringToString()
99{
100returnstring.Format(
101"Begin[{0}],End[{1}],Weight[{2}]",
102Begin,End,Weight);
103}
104}
105
106classGraph
107{
108privateDictionary>_adjacentEdges
109=newDictionary>();
110
111publicGraph(intvertexCount)
112{
113this.VertexCount=vertexCount;
114}
115
116publicintVertexCount{get;privateset;}
117
118publicintEdgeCount
119{
120get
121{
122return_adjacentEdges.Values.SelectMany(e=>e).Count();
123}
124}
125
126publicvoidAddEdge(intbegin,intend,intweight)
127{
128if(!_adjacentEdges.ContainsKey(begin))
129{
130varedges=newList();
131_adjacentEdges.Add(begin,edges);
132}
133
134_adjacentEdges[begin].Add(newEdge(begin,end,weight));
135}
136
137publicvoidAddEdge(Edgeedge)
138{
139AddEdge(edge.Begin,edge.End,edge.Weight);
140}
141
142publicvoidAddEdges(IEnumerableedges)
143{
144foreach(varedgeinedges)
145{
146AddEdge(edge);
147}
148}
149
150publicIEnumerableGetAllEdges()
151{
152return_adjacentEdges.Values.SelectMany(e=>e);
153}
154
155publicint[,]Johnsons()
156{
157//distSet[,]willbetheoutputmatrixthatwillfinallyhavetheshortest
158//distancesbetweeneverypairofvertices
159int[,]distSet=newint[VertexCount,VertexCount];
160
161for(inti=0;i
162{
163for(intj=0;j
164{
165distSet[i,j]=int.MaxValue;
166}
167}
168for(inti=0;i
169{
170distSet[i,i]=0;
171}
172
173//step1:addnewvertexsandconnecttoallvertices
174Graphg=newGraph(this.VertexCount+1);
175g.AddEdges(this.GetAllEdges());
176
177ints=this.VertexCount;
178for(inti=0;i
179{
180g.AddEdge(s,i,0);
181}
182
183//step2:useBellman-Fordtoevaluateshortestpathsfroms
184int[]h=g.BellmanFord(s);
185
186//step3:re-weightingedgesoftheoriginalgraph
187//w(u,v)=w(u,v)+(h[u]-h[v])
188foreach(varedgeinthis.GetAllEdges())
189{
190edge.Reweight(edge.Weight+(h[edge.Begin]-h[edge.End]));
191}
192
193//step4:useDijkstraforeachedges
194for(intbegin=0;begin
195{
196int[]dist=this.Dijkstra(begin);
197for(intend=0;end
198{
199if(dist[end]!=int.MaxValue)
200{
201distSet[begin,end]=dist[end]-(h[begin]-h[end]);
202}
203}
204}
205
206returndistSet;
207}
208
209publicint[,]FloydWarshell()
210{
211/distSet[,]willbetheoutputmatrixthatwillfinallyhavetheshortest
212distancesbetweeneverypairofvertices/
213int[,]distSet=newint[VertexCount,VertexCount];
214
215for(inti=0;i
216{
217for(intj=0;j
218{
219distSet[i,j]=int.MaxValue;
220}
221}
222for(inti=0;i
223{
224distSet[i,i]=0;
225}
226
227/Initializethesolutionmatrixsameasinputgraphmatrix.Or
228wecansaytheinitialvaluesofshortestdistancesarebased
229onshortestpathsconsideringnointermediatevertex./
230foreach(varedgein_adjacentEdges.Values.SelectMany(e=>e))
231{
232distSet[edge.Begin,edge.End]=edge.Weight;
233}
234
235/Addallverticesonebyonetothesetofintermediatevertices.
236--->Beforestartofaiteration,wehaveshortestdistancesbetweenall
237pairsofverticessuchthattheshortestdistancesconsideronlythe
238verticesinset{0,1,2,..k-1}asintermediatevertices.
239--->Aftertheendofaiteration,vertexno.kisaddedtothesetof
240intermediateverticesandthesetbecomes{0,1,2,..k}/
241for(intk=0;k
242{
243//Pickallverticesassourceonebyone
244for(inti=0;i
245{
246//Pickallverticesasdestinationfortheabovepickedsource
247for(intj=0;j
248{
249//Ifvertexkisontheshortestpathfrom
250//itoj,thenupdatethevalueofdistSet[i,j]
251if(distSet[i,k]!=int.MaxValue
252&&distSet[k,j]!=int.MaxValue
253&&distSet[i,k]+distSet[k,j]
254{
255distSet[i,j]=distSet[i,k]+distSet[k,j];
256}
257}
258}
259}
260
261returndistSet;
262}
263
264publicint[]BellmanFord(intsource)
265{
266//distSet[i]willholdtheshortestdistancefromsourcetoi
267int[]distSet=newint[VertexCount];
268
269//Step1:InitializedistancesfromsourcetoallotherverticesasINFINITE
270for(inti=0;i
271{
272distSet[i]=int.MaxValue;
273}
274distSet[source]=0;
275
276//Step2:Relaxalledges|V|-1times.Asimpleshortestpathfromsource
277//toanyothervertexcanhaveat-most|V|-1edges
278for(inti=1;i<=VertexCount-1;i++)
279{
280foreach(varedgein_adjacentEdges.Values.SelectMany(e=>e))
281{
282intu=edge.Begin;
283intv=edge.End;
284intweight=edge.Weight;
285
286if(distSet[u]!=int.MaxValue
287&&distSet[u]+weight
288{
289distSet[v]=distSet[u]+weight;
290}
291}
292}
293
294//Step3:checkfornegative-weightcycles.Theabovestepguarantees
295//shortestdistancesifgraphdoesn''tcontainnegativeweightcycle.
296//Ifwegetashorterwww.wang027.compath,thenthereisacycle.
297foreach(varedgein_adjacentEdges.Values.SelectMany(e=>e))
298{
299intu=edge.Begin;
300intv=edge.End;
301intweight=edge.Weight;
302
303if(distSet[u]!=int.MaxValue
304&&distSet[u]+weight
305{
306Console.WriteLine("Graphcontainsnegativeweightcycle.");
307}
308}
309
310returndistSet;
311}
312
313publicint[]Dijkstra(intsource)
314{
315//dist[i]willholdtheshortestdistancefromsourcetoi
316int[]distSet=newint[VertexCount];
317
318//sptSet[i]willtrueifvertexiisincludedinshortest
319//pathtreeorshortestdistancefromsourcetoiisfinalized
320bool[]sptSet=newbool[VertexCount];
321
322//initializealldistancesasINFINITEandstpSet[]asfalse
323for(inti=0;i
324{
325distSet[i]=int.MaxValue;
326sptSet[i]=false;
327}
328
329//distanceofsourcevertexfromitselfisalways0
330distSet[source]=0;
331
332//findshortestpathforallvertices
333for(inti=0;i
334{
335//picktheminimumdistancevertexfromthesetofverticesnot
336//yetprocessed.uisalwaysequaltosourceinfirstiteration.
337intu=CalculateMinDistance(distSet,sptSet);
338
339//markthepickedvertexasprocessed
340sptSet[u]=true;
341
342//updatedistvalueoftheadjacentverticesofthepickedvertex.
343for(intv=0;v
344{
345//updatedist[v]onlyifisnotinsptSet,thereisanedgefrom
346//utov,andtotalweightofpathfromsourcetovthroughuis
347//smallerthancurrentvalueofdist[v]
348if(!sptSet[v]
349&&distSet[u]!=int.MaxValue
350&&_adjacentEdges.ContainsKey(u)
351&&_adjacentEdges[u].Exists(e=>e.End==v))
352{
353intd=_adjacentEdges[u].Single(e=>e.End==v).Weight;
354if(distSet[u]+d
355{
356distSet[v]=distSet[u]+d;
357}
358}
359}
360}
361
362returndistSet;
363}
364
365privateintCalculateMinDistance(int[]distSet,bool[]sptSet)
366{
367intminDistance=int.MaxValue;
368intminDistanceIndex=-1;
369
370for(intv=0;v
371{
372if(!sptSet[v]&&distSet[v]<=minDistance)
373{
374minDistance=distSet[v];
375minDistanceIndex=v;
376}
377}
378
379returnminDistanceIndex;
380}
381}
382}
383}
|
|
