All pairs shortest paths
We want the shortest path between every pair of nodes. On sparse graphs, running a fast single source routine from each node would be ideal, but the fast routine fails when some edges have negative weights. Johnson's algorithm fixes this with a clever reweighting.
Reweighting with potentials
First add a temporary node with a zero weight edge to every other node. Run a routine that tolerates negatives, such as Bellman Ford, from this node to get a value, a potential, for each node.
- Replace each edge weight with the old weight plus the source potential minus the target potential.
- Every reweighted edge is now nonnegative.
- Crucially, the shortest paths stay the same, only their recorded length shifts.
Then run Dijkstra everywhere
With all weights nonnegative, run the fast nonnegative shortest path routine from each node. Finally undo the shift on each computed distance to recover true lengths. If the initial Bellman Ford detects a negative cycle, the problem has no finite answer and we stop.
Key idea
Use node potentials from Bellman Ford to make all edges nonnegative, then run a fast routine from each node and undo the shift.