Johnson’s Algorithm

When tasked with finding the shortest paths between all pairs of vertices, calculating the shortest paths between them seems easy enough. In the presence of negative edge weights, our first instinct is to call the Bellman-Ford algorithm from each vertex.

This would certainly guarantee the detection of negative-weight cycles in the digraph. On the other hand, it would take a whopping $O(n^4)$ time in the worst case.worstcasejohnson

Johnson’s algorithm refines this idea of using a single-source shortest-paths algorithm from each vertex to solve the all-pairs shortest-paths problem. The algorithm is named after Donald B. Johnson, who is also credited with generalizing binary heaps to $d$-ary heaps.

The central idea

The central idea behind Johnson’s algorithm is to transform the edge weights so that:

1. The new edge weights are nonnegative.
2. The shortest paths with respect to the new weights are exactly the shortest paths with respect to the old weights.

Such a reweighting enables us to use the more efficient Dijkstra’s algorithm instead of the Bellman-Ford algorithm from each vertex. Of course, we also need to be sure that the all pairs shortest-paths problem is well-defined for the digraph. So, let’s get that out of the way first.

Motivation for a new vertex

If a negative-weight cycle is present in the graph at all, that’s a problem. Running the Bellman-Ford algorithm from an arbitrary vertex only detects the negative-weight cycles reachable from that vertex.

We can obtain a digraph $H$ from $G$ by creating a new vertex $s$ and adding zero-weight edges from $s$ to all other vertices of $G$. We observe that no new cycle is created in $H$ (since $s$ has no incoming edges). As all vertices in $H$ are reachable from $s$, running the Bellman-Ford algorithm—just once—from $s$ is guaranteed to detect the presence of any negative-weight cycles in $H$ and, therefore, in $G$.

We show a digraph $H$ constructed in this manner from the digraph above:

In the absence of a negative-weight cycle, we can proceed with the idea of reweighting the edges.

The scheme for reweighting an edge

For each edge, we want to transform its weight by adding some quantity to it. We already ruled out in an earlier exercise that adding some fixed constant doesn’t work.

The telescoping effect

Consider this scheme:

• Assign an arbitrary number to each vertex.
• For each edge, $e$, change its weight by adding to it the difference of the number assigned to its head from the number assigned to its tail.

Consider a path $\langle v_0, v_1, \cdots, v_k \rangle$ with some number $a_i$ ...