首页 > 代码库 > Johnson 全源最短路径算法
Johnson 全源最短路径算法
解决单源最短路径问题（Single Source Shortest Paths Problem）的算法包括：
- Dijkstra 单源最短路径算法：时间复杂度为 O(E + VlogV)，要求权值非负；
- Bellman-Ford 单源最短路径算法：时间复杂度为 O(VE)，适用于带负权值情况；
对于全源最短路径问题（All-Pairs Shortest Paths Problem），可以认为是单源最短路径问题的推广，即分别以每个顶点作为源顶点并求其至其它顶点的最短距离。例如，对每个顶点应用 Bellman-Ford 算法，则可得到所有顶点间的最短路径的运行时间为 O(V2E)，由于图中顶点都是连通的，而边的数量可能会比顶点更多，这个时间没有比 Floyd-Warshall 全源最短路径算法 O(V3) 更优。那么，再试下对每个顶点应用 Dijkstra 算法，则可得到所有顶点间的最短路径的运行时间为 O(VE + V2logV)，看起来优于 Floyd-Warshall 算法的 O(V3)，所以看起来使用基于 Dijkstra 算法的改进方案好像更好，但问题是 Dijkstra 算法要求图中所有边的权值非负，不适合通用的情况。
在 1977 年，Donald B. Johnson 提出了对所有边的权值进行 "re-weight" 的算法，使得边的权值非负，进而可以使用 Dijkstra 算法进行最短路径的计算。
我们先自己思考下如何进行 "re-weight" 操作，比如，简单地对每条边的权值加上一个较大的正数，使其非负，是否可行？
1 1 1s-----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# 代码实现如下：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 5 namespace GraphAlgorithmTesting 6 { 7 class Program 8 { 9 static void Main(string[] args) 10 { 11 // build a directed and negative weighted graph 12 Graph directedGraph1 = new Graph(5); 13 directedGraph1.AddEdge(0, 1, -1); 14 directedGraph1.AddEdge(0, 2, 4); 15 directedGraph1.AddEdge(1, 2, 3); 16 directedGraph1.AddEdge(1, 3, 2); 17 directedGraph1.AddEdge(1, 4, 2); 18 directedGraph1.AddEdge(3, 2, 5); 19 directedGraph1.AddEdge(3, 1, 1); 20 directedGraph1.AddEdge(4, 3, -3); 21 22 Console.WriteLine(); 23 Console.WriteLine("Graph Vertex Count : {0}", directedGraph1.VertexCount); 24 Console.WriteLine("Graph Edge Count : {0}", directedGraph1.EdgeCount); 25 Console.WriteLine(); 26 27 int[,] distSet1 = directedGraph1.Johnsons(); 28 PrintSolution(directedGraph1, distSet1); 29 30 // build a directed and positive weighted graph 31 Graph directedGraph2 = new Graph(4); 32 directedGraph2.AddEdge(0, 1, 5); 33 directedGraph2.AddEdge(0, 3, 10); 34 directedGraph2.AddEdge(1, 2, 3); 35 directedGraph2.AddEdge(2, 3, 1); 36 37 Console.WriteLine(); 38 Console.WriteLine("Graph Vertex Count : {0}", directedGraph2.VertexCount); 39 Console.WriteLine("Graph Edge Count : {0}", directedGraph2.EdgeCount); 40 Console.WriteLine(); 41 42 int[,] distSet2 = directedGraph2.Johnsons(); 43 PrintSolution(directedGraph2, distSet2); 44 45 Console.ReadKey(); 46 } 47 48 private static void PrintSolution(Graph g, int[,] distSet) 49 { 50 Console.Write("\t"); 51 for (int i = 0; i < g.VertexCount; i++) 52 { 53 Console.Write(i + "\t"); 54 } 55 Console.WriteLine(); 56 Console.Write("\t"); 57 for (int i = 0; i < g.VertexCount; i++) 58 { 59 Console.Write("-" + "\t"); 60 } 61 Console.WriteLine(); 62 for (int i = 0; i < g.VertexCount; i++) 63 { 64 Console.Write(i + "|\t"); 65 for (int j = 0; j < g.VertexCount; j++) 66 { 67 if (distSet[i, j] == int.MaxValue) 68 { 69 Console.Write("INF" + "\t"); 70 } 71 else 72 { 73 Console.Write(distSet[i, j] + "\t"); 74 } 75 } 76 Console.WriteLine(); 77 } 78 } 79 80 class Edge 81 { 82 public Edge(int begin, int end, int weight) 83 { 84 this.Begin = begin; 85 this.End = end; 86 this.Weight = weight; 87 } 88 89 public int Begin { get; private set; } 90 public int End { get; private set; } 91 public int Weight { get; private set; } 92 93 public void Reweight(int newWeight) 94 { 95 this.Weight = newWeight; 96 } 97 98 public override string ToString() 99 {100 return string.Format(101 "Begin[{0}], End[{1}], Weight[{2}]",102 Begin, End, Weight);103 }104 }105 106 class Graph107 {108 private Dictionary<int, List<Edge>> _adjacentEdges109 = new Dictionary<int, List<Edge>>();110 111 public Graph(int vertexCount)112 {113 this.VertexCount = vertexCount;114 }115 116 public int VertexCount { get; private set; }117 118 public int EdgeCount119 {120 get121 {122 return _adjacentEdges.Values.SelectMany(e => e).Count();123 }124 }125 126 public void AddEdge(int begin, int end, int weight)127 {128 if (!_adjacentEdges.ContainsKey(begin))129 {130 var edges = new List<Edge>();131 _adjacentEdges.Add(begin, edges);132 }133 134 _adjacentEdges[begin].Add(new Edge(begin, end, weight));135 }136 137 public void AddEdge(Edge edge)138 {139 AddEdge(edge.Begin, edge.End, edge.Weight);140 }141 142 public void AddEdges(IEnumerable<Edge> edges)143 {144 foreach (var edge in edges)145 {146 AddEdge(edge);147 }148 }149 150 public IEnumerable<Edge> GetAllEdges()151 {152 return _adjacentEdges.Values.SelectMany(e => e);153 }154 155 public int[,] Johnsons()156 {157 // distSet[,] will be the output matrix that will finally have the shortest 158 // distances between every pair of vertices159 int[,] distSet = new int[VertexCount, VertexCount];160 161 for (int i = 0; i < VertexCount; i++)162 {163 for (int j = 0; j < VertexCount; j++)164 {165 distSet[i, j] = int.MaxValue;166 }167 }168 for (int i = 0; i < VertexCount; i++)169 {170 distSet[i, i] = 0;171 }172 173 // step 1: add new vertex s and connect to all vertices174 Graph g = new Graph(this.VertexCount + 1);175 g.AddEdges(this.GetAllEdges());176 177 int s = this.VertexCount;178 for (int i = 0; i < this.VertexCount; i++)179 {180 g.AddEdge(s, i, 0);181 }182 183 // step 2: use Bellman-Ford to evaluate shortest paths from s184 int[] h = g.BellmanFord(s);185 186 // step 3: re-weighting edges of the original graph187 // w(u, v) = w(u, v) + (h[u] - h[v])188 foreach (var edge in this.GetAllEdges())189 {190 edge.Reweight(edge.Weight + (h[edge.Begin] - h[edge.End]));191 }192 193 // step 4: use Dijkstra for each edges194 for (int begin = 0; begin < this.VertexCount; begin++)195 {196 int[] dist = this.Dijkstra(begin);197 for (int end = 0; end < dist.Length; end++)198 {199 if (dist[end] != int.MaxValue)200 {201 distSet[begin, end] = dist[end] - (h[begin] - h[end]);202 }203 }204 }205 206 return distSet;207 }208 209 public int[,] FloydWarshell()210 {211 /* distSet[,] will be the output matrix that will finally have the shortest 212 distances between every pair of vertices */213 int[,] distSet = new int[VertexCount, VertexCount];214 215 for (int i = 0; i < VertexCount; i++)216 {217 for (int j = 0; j < VertexCount; j++)218 {219 distSet[i, j] = int.MaxValue;220 }221 }222 for (int i = 0; i < VertexCount; i++)223 {224 distSet[i, i] = 0;225 }226 227 /* Initialize the solution matrix same as input graph matrix. Or 228 we can say the initial values of shortest distances are based229 on shortest paths considering no intermediate vertex. */230 foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))231 {232 distSet[edge.Begin, edge.End] = edge.Weight;233 }234 235 /* Add all vertices one by one to the set of intermediate vertices.236 ---> Before start of a iteration, we have shortest distances between all237 pairs of vertices such that the shortest distances consider only the238 vertices in set {0, 1, 2, .. k-1} as intermediate vertices.239 ---> After the end of a iteration, vertex no. k is added to the set of240 intermediate vertices and the set becomes {0, 1, 2, .. k} */241 for (int k = 0; k < VertexCount; k++)242 {243 // Pick all vertices as source one by one244 for (int i = 0; i < VertexCount; i++)245 {246 // Pick all vertices as destination for the above picked source247 for (int j = 0; j < VertexCount; j++)248 {249 // If vertex k is on the shortest path from250 // i to j, then update the value of distSet[i,j]251 if (distSet[i, k] != int.MaxValue252 && distSet[k, j] != int.MaxValue253 && distSet[i, k] + distSet[k, j] < distSet[i, j])254 {255 distSet[i, j] = distSet[i, k] + distSet[k, j];256 }257 }258 }259 }260 261 return distSet;262 }263 264 public int[] BellmanFord(int source)265 {266 // distSet[i] will hold the shortest distance from source to i267 int[] distSet = new int[VertexCount];268 269 // Step 1: Initialize distances from source to all other vertices as INFINITE270 for (int i = 0; i < VertexCount; i++)271 {272 distSet[i] = int.MaxValue;273 }274 distSet[source] = 0;275 276 // Step 2: Relax all edges |V| - 1 times. A simple shortest path from source277 // to any other vertex can have at-most |V| - 1 edges278 for (int i = 1; i <= VertexCount - 1; i++)279 {280 foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))281 {282 int u = edge.Begin;283 int v = edge.End;284 int weight = edge.Weight;285 286 if (distSet[u] != int.MaxValue287 && distSet[u] + weight < distSet[v])288 {289 distSet[v] = distSet[u] + weight;290 }291 }292 }293 294 // Step 3: check for negative-weight cycles. The above step guarantees295 // shortest distances if graph doesn‘t contain negative weight cycle.296 // If we get a shorter path, then there is a cycle.297 foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))298 {299 int u = edge.Begin;300 int v = edge.End;301 int weight = edge.Weight;302 303 if (distSet[u] != int.MaxValue304 && distSet[u] + weight < distSet[v])305 {306 Console.WriteLine("Graph contains negative weight cycle.");307 }308 }309 310 return distSet;311 }312 313 public int[] Dijkstra(int source)314 {315 // dist[i] will hold the shortest distance from source to i316 int[] distSet = new int[VertexCount];317 318 // sptSet[i] will true if vertex i is included in shortest319 // path tree or shortest distance from source to i is finalized320 bool[] sptSet = new bool[VertexCount];321 322 // initialize all distances as INFINITE and stpSet[] as false323 for (int i = 0; i < VertexCount; i++)324 {325 distSet[i] = int.MaxValue;326 sptSet[i] = false;327 }328 329 // distance of source vertex from itself is always 0330 distSet[source] = 0;331 332 // find shortest path for all vertices333 for (int i = 0; i < VertexCount - 1; i++)334 {335 // pick the minimum distance vertex from the set of vertices not336 // yet processed. u is always equal to source in first iteration.337 int u = CalculateMinDistance(distSet, sptSet);338 339 // mark the picked vertex as processed340 sptSet[u] = true;341 342 // update dist value of the adjacent vertices of the picked vertex.343 for (int v = 0; v < VertexCount; v++)344 {345 // update dist[v] only if is not in sptSet, there is an edge from 346 // u to v, and total weight of path from source to v through u is 347 // smaller than current value of dist[v]348 if (!sptSet[v]349 && distSet[u] != int.MaxValue350 && _adjacentEdges.ContainsKey(u)351 && _adjacentEdges[u].Exists(e => e.End == v))352 {353 int d = _adjacentEdges[u].Single(e => e.End == v).Weight;354 if (distSet[u] + d < distSet[v])355 {356 distSet[v] = distSet[u] + d;357 }358 }359 }360 }361 362 return distSet;363 }364 365 private int CalculateMinDistance(int[] distSet, bool[] sptSet)366 {367 int minDistance = int.MaxValue;368 int minDistanceIndex = -1;369 370 for (int v = 0; v < VertexCount; v++)371 {372 if (!sptSet[v] && distSet[v] <= minDistance)373 {374 minDistance = distSet[v];375 minDistanceIndex = v;376 }377 }378 379 return minDistanceIndex;380 }381 }382 }383 }
运行结果如下：
参考资料
- 广度优先搜索
- 深度优先搜索
- Breadth First Traversal for a Graph
- Depth First Traversal for a Graph
- Dijkstra 单源最短路径算法
- Bellman-Ford 单源最短路径算法
- Bellman–Ford algorithm
- Introduction To Algorithm
- Floyd-Warshall‘s algorithm
- Bellman-Ford algorithm for single-source shortest paths
- Dynamic Programming | Set 23 (Bellman–Ford Algorithm)
- Dynamic Programming | Set 16 (Floyd Warshall Algorithm)
- Johnson’s algorithm for All-pairs shortest paths
- Floyd-Warshall‘s algorithm
- 最短路径算法--Dijkstra算法，Bellmanford算法，Floyd算法，Johnson算法
- QuickGraph, Graph Data Structures And Algorithms for .NET
- CHAPTER 26: ALL-PAIRS SHORTEST PATHS
本篇文章《Johnson 全源最短路径算法》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。
Johnson 全源最短路径算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。