# Johnson's Algorithm For Sparse Graphs

#### 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* = *d _{ij}*, where

*d*=

_{ij}*δ*(

*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 computeG′, whereV[G′] =V[G] ∪ {s},E[G′] =E[G] ∪ {(s,v) :v∈V[G]}, andw(s,v) = 0 for allv∈V[G] 2ifBELLMAN-FORD(G′,w,s) = FALSE 3thenprint "the input graph contains a negative-weight cycle" 4else foreach vertexv∈V[G′] 5doseth(v) to the value ofδ(s,v) computed by the Bellman-Ford algorithm 6foreach edge (u,v) ∈E[G′] 7do

8foreach vertexu∈V[G] 9dorun DIJKSTRA(G,

,u) to compute

for allv∈V[G] 10foreach vertexv∈V[G] 11do

12returnD

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 *d _{uv}* 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*(*V*^{2} 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.