SKEDSOFT

Design Analysis Of Algorithm

Computing all-pairs shortest paths

Johnson's algorithm to compute all-pairs shortest paths uses the Bellman-Ford algorithm and Dijkstra's algorithm as subroutines. It assumes that the edges are stored in adjacency lists. The algorithm returns the usual |V| × |V| matrix D = dij, where dij = δ(i, j), or it reports that the input graph contains a negative-weight cycle. As is typical for an all-pairs shortest-paths algorithm, we assume that the vertices are numbered from 1 to |V|.

	JOHNSON(G)
 1  compute G, where V[G] = V[G]  {s},
           E[G] = E[G]  {(s, v) : v  V[G]}, and
           w(s, v) = 0 for all v  V[G]
 2  if BELLMAN-FORD(G, w, s) = FALSE
 3     then print "the input graph contains a negative-weight cycle"
 4     else for each vertex v  V[G]
 5              do set h(v) to the value of δ(s, v)
                           computed by the Bellman-Ford algorithm
 6          for each edge (u, v)  E[G]
 7              do 
	8          for each vertex u  V[G]
 9              do run DIJKSTRA(G, 
	, u) to compute 
	for all v  V[G]
10                 for each vertex v  V[G]
11                     do 
	12          return D

This code simply performs the actions we specified earlier. Line 1 produces G. Line 2 runs the Bellman-Ford algorithm on G with weight function w and source vertex s. If G, and hence G, contains a negative-weight cycle, line 3 reports the problem. Lines 4-11 assume that G contains no negative-weight cycles. Lines 4-5 set h(v) to the shortest-path weight δ(s, v) computed by the Bellman-Ford algorithm for all v V. Lines 6-7 compute the new weights . For each pair of vertices u, v V , the for loop of lines 8-11 computes the shortest-path weight by calling Dijkstra's algorithm once from each vertex in V. Line 11 stores in matrix entry duv the correct shortest-path weight δ(u, v), calculated using equation (25.10). Finally, line 12 returns the completed D matrix. Figure 25.6 shows the execution of Johnson's algorithm.

If the min-priority queue in Dijkstra's algorithm is implemented by a Fibonacci heap, the running time of Johnson's algorithm is O(V2 lg V V E). The simpler binary min-heap implementation yields a running time of O(V E lg V), which is still asymptotically faster than the Floyd-Warshall algorithm if the graph is sparse.