Johnson’s Algorithm

Overview of Johnson’s all-pairs shortest path algorithm

Johnson’s all-pairs shortest path algorithm computes a cost $π(v)$ for each vertex so that the new weight of every edge is non-negative and then computes shortest paths with respect to the new weights using Dijkstra’s algorithm.

First, suppose the input graph has a vertex $s$ that can reach all the other vertices. Johnson’s algorithm computes the shortest paths from $s$ to the other vertices, using Bellman-Ford (which doesn’t care if the edge weights are negative), and then reweights the graph using the price function $π(v) = dist(s, v)$. The new weight of every edge is:

$$w′(u\rightarrow v) = dist(s, u) + w(u\rightarrow v) − dist(s, v).$$

Non-negative weights

These new weights are non-negative because Bellman-Ford halted! Recall that an edge $u\rightarrow v$ is tense if $dist(s, u) + w(u\rightarrow v) < dist(s, v)$ and that single-source shortest path algorithms eliminate all tense edges. (If Bellman-Ford detects a negative cycle, Johnson’s algorithm aborts because shortest paths are not well-defined.)

If there is no suitable vertex $s$ that can reach everything, then no matter where we start Bellman-Ford, some of the resulting vertex prices will be infinite. To avoid this issue, we always add a new vertex $s$ to the graph with zero-weight edges from $s$ to the other vertices but no edges going back into $s$. This addition doesn’t change the shortest paths between any pair of original vertices because there are no paths into $s$.

The complete pseudocode for Johnson’s algorithm is shown below. The running time of this algorithm is dominated by the calls to Dijkstra’s algorithm. Specifically, we spend $O(VE)$ time running Bellman-Ford once, $O(VE\log V )$ time running Dijkstra $V$ times, and $O(V + E)$ time doing other bookkeeping. Thus, the overall running time is $O(VE\log V)=O(V^3\log V)$. Negative edges don’t slow us down after all!