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.