The goal
Johnson computes shortest paths between all pairs of nodes, and it stays efficient on sparse graphs that may contain negative edges but no negative cycle.
Reweighting
Dijkstra cannot handle negative edges directly. Johnson sidesteps this by giving each node a potential value, then defining a new weight for every edge as the old weight plus the source potential minus the target potential. With well chosen potentials, every reweighted edge becomes non negative, yet the shortest paths are preserved.
The potentials come from running Bellman Ford once from an added super source connected to all nodes with zero weight.
- Add a super source and run Bellman Ford to get potentials.
- Reweight every edge to be non negative.
- Run Dijkstra from each node on the reweighted graph.
- Undo the offset to recover true distances.
Key idea
Johnson reweights edges using node potentials from one Bellman Ford pass so that Dijkstra can run from every source, making all pairs shortest paths fast on sparse graphs even with some negative edges.