Algo: Johnson's All-Pairs Shortest Path

Finding the shortest path between every pair of vertices in a graph is a foundational problem with applications in logistics, networking, and spatial analysis. When graphs contain negative edge weights, common workhorses like Dijkstra's algorithm fail, leaving you with slower, less efficient options. Johnson's algorithm elegantly solves this by temporarily transforming the graph to eliminate negative weights, unlocking the speed of Dijkstra's algorithm for all vertices. This makes it the most efficient known method for computing all-pairs shortest paths in sparse graphs that may contain negative weights but no negative cycles.

The Core Problem and Intuition for Reweighting

The all-pairs shortest path problem asks: for every pair of vertices $u$ and $v$ in a graph $G$, what is the shortest possible distance from $u$ to $v$? For graphs with only non-negative weights, you could simply run Dijkstra's algorithm from each vertex. However, Dijkstra's algorithm fails in the presence of negative edge weights. For graphs with negative weights, the Bellman-Ford algorithm works but is slower, taking $O(VE)$ time per source vertex. Running it from all vertices leads to a total complexity of $O(V^{2}E)$, which is prohibitively slow for large, sparse graphs.

Johnson's insight was to use a reweighting technique. The goal is to assign a new, non-negative weight to every edge so that the shortest-path relationships between all pairs of vertices are preserved. If we can do this, we can then safely run Dijkstra's algorithm on the reweighted graph. The transformation uses a potential function, often denoted as $h(v)$, which is assigned to each vertex. The new weight $\hat{w}(u,v)$ for an edge from $u$ to $v$ is defined as: $$\hat{w}(u,v)=w(u,v)+h(u)-h(v)$$

The critical property of this reweighting is that for any path $p$ from vertex $s$ to vertex $t$, the reweighted path length differs from the original path length by a constant: $h(s)-h(t)$. Since this constant depends only on the start and end vertices, and not on the path itself, the shortest path in the original graph remains the shortest in the reweighted graph.

Step-by-Step Algorithm and Implementation

Johnson's algorithm proceeds in three distinct stages. A proper implementation must handle each stage carefully to achieve the advertised $O(VE+V^2\log V)$ time complexity for graphs using adjacency lists.

Step 1: Add a New Source Vertex. Add a new vertex $s$ to the graph and connect it with a zero-weight edge to every other original vertex. This creates a modified graph $G^{\prime }$.

Step 2: Run Bellman-Ford to Compute Potentials. Run the Bellman-Ford algorithm from the new source vertex $s$ on graph $G^{\prime }$. The shortest distance from $s$ to each original vertex $v$, as computed by Bellman-Ford, becomes our potential $h(v)$. If Bellman-Ford detects a negative-weight cycle in $G^{\prime }$, then the original graph $G$ also contains a negative-weight cycle reachable from some vertex, and the algorithm halts, as all-pairs shortest paths are not defined.

Step 3: Reweight Edges and Run Dijkstra. Now, for each original edge $(u,v)$ with original weight $w(u,v)$, compute its new non-negative weight: $\hat{w}(u,v)=w(u,v)+h(u)-h(v)$. The property of the potentials guarantees $\hat{w}(u,v)\ge 0$. Finally, for each vertex $u$ in the original graph, run Dijkstra's algorithm using the reweighted edge weights $\hat{w}$. To recover the true shortest path distance $\delta (u,v)$, you must adjust the result from Dijkstra, denoted $d_{\hat{w}}(u,v)$: $$\delta (u,v)=d_{\hat{w}}(u,v)-h(u)+h(v)$$

Complexity Analysis: Sparse vs. Dense Graphs

Understanding the time complexity reveals when to choose Johnson's algorithm over alternatives like Floyd-Warshall.

• Step 1 (Adding vertex): $O(V)$.
• Step 2 (Bellman-Ford): $O(VE)$.
• Step 3 (Reweighting & V runs of Dijkstra): Reweighting all edges is $O(E)$. Running Dijkstra from each vertex, using a binary min-heap, costs $O(V\cdot (E\log V))=O(VE\log V)$.

This gives a total of $O(VE\log V)$. However, for sparse graphs where $E$ is $O(V)$, this simplifies to $O(V^2\log V)$. With a Fibonacci heap, Dijkstra's complexity improves to $O(E+V\log V)$, making Johnson's total complexity $O(VE+V^2\log V)$.

Now, compare this to the Floyd-Warshall algorithm, which runs in a fixed $\Theta (V^3)$ time and works with negative weights (but no negative cycles).

• For Sparse Graphs ($E\approx V$): Johnson's ($O(V^2\log V)$) is asymptotically faster than Floyd-Warshall ($O(V^3)$).
• For Dense Graphs ($E\approx V^2$): Floyd-Warshall's $O(V^3)$ is comparable to Johnson's $O(V^3+V^2\log V)$ or $O(V^3\log V)$, making Floyd-Warshall often simpler and with a lower constant factor. The decision hinges on graph density and the need for Dijkstra's efficiency on the reweighted graph.

Common Pitfalls

1. Misunderstanding the Reweighting Guarantee: A common mistake is thinking the reweighted path weight equals the original path weight. It does not; it is offset by $h(start)-h(end)$. You must reverse the reweighting after running Dijkstra to get the correct distance. Forgetting this final adjustment yields incorrect results.

1. Incorrect Graph Modification for Bellman-Ford: The new source vertex $s$ must have a zero-weight edge to every other vertex, not just one. This ensures Bellman-Ford can find a valid potential $h(v)$ for every vertex, even those in disconnected components of a directed graph. Using a single edge or an arbitrary vertex as the source can fail to produce correct potentials for all vertices.

1. Ignoring Negative Cycle Detection: The algorithm's first step is not just to compute potentials; it's a vital detection phase. If Bellman-Ford finds a negative-weight cycle in $G^{\prime }$, the original graph $G$ has a reachable negative cycle, meaning shortest paths are not well-defined. Proceeding to the Dijkstra phase would be meaningless. Your implementation must check and handle this case explicitly.

1. Inefficient Data Structures for Sparse Graphs: Implementing this for a sparse graph but using an adjacency matrix for Dijkstra pushes its complexity to $O(V^2)$ per run, making the total $O(V^3)$ and negating Johnson's advantage. Always use an adjacency list paired with a priority queue (min-heap) to achieve the $O(E\log V)$ per-Dijkstra performance critical for sparse graphs.

Summary

• Johnson's algorithm solves the all-pairs shortest paths problem for graphs that may have negative edge weights but no negative cycles by using a reweighting technique with vertex potentials $h(v)$.
• The algorithm works by adding a dummy source, using Bellman-Ford to compute potentials that make all edge weights non-negative, then running Dijkstra's algorithm from every vertex on the transformed graph.
• Its time complexity of $O(VE+V^2\log V)$ makes it asymptotically superior to the $\Theta (V^3)$ Floyd-Warshall algorithm for sparse graphs, while Floyd-Warshall remains a competitive, simpler choice for dense graphs.
• The reweighting preserves shortest paths because all paths between two vertices have their lengths changed by the same constant ($h(start)-h(end)$), requiring a final adjustment to Dijkstra's output to obtain the true distances.
• Successful implementation requires careful handling of the dummy vertex, robust negative cycle detection, and the use of efficient adjacency lists and priority queues to realize the theoretical performance benefits.