Johnson's Algorithm

Johnson's Algorithm computes shortest paths between all pairs of vertices in a sparse weighted graph by reweighting edges to eliminate negative weights, then running Dijkstra from each vertex. The reweighting uses Bellman-Ford to compute a potential function derived from a dummy source connected to all vertices. If Bellman-Ford detects a negative weight cycle, Johnson's aborts: the all-pairs problem is ill-posed.

The algorithm's \(O(V^2 \log V + VE)\) complexity with Fibonacci heaps beats the \(O(V^3)\) of Floyd-Warshall for sparse graphs, making it the algorithm of choice for road networks and sparse communication topologies.

Johnson's insight was not merely technical. It showed that a global transformation — reweighting — can make a problem tractable for local methods. This is the algorithmic analog of institutional design: restructure the incentives, then let decentralized optimization proceed. The algorithm is a proof that global coordination and local computation are not enemies but partners, provided the global structure is designed correctly.