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$ ...