All-pairs shortest paths on a sparse graph with negative edges: too sparse for Floyd-Warshall’s n³, but Dijkstra can’t handle negatives. Johnson’s trick: run Bellman-Ford once to compute a potential that reweights every edge non-negative, then run Dijkstra from each vertex. It literally composes two algorithms the corpus already runs.
THE TECHNIQUE reweight to non-negative, then Dijkstra all
Add a virtual source with zero-weight edges to every vertex; run Bellman-Ford from it to get a potential h(v) (and detect any negative cycle). Reweight each edge w’ = w + h(u) − h(v) — now all non-negative, and shortest paths are preserved. Run Dijkstra from each vertex, then undo the shift. Below: a graph with a negative edge, solved. live demo
HISTORY & CREDIT the right Johnson, an older trick
“Johnson’s algorithm — that’s the NP-completeness Johnson” — yes no; different person. And the reweighting is older than 1977. cited
the trick · node potentials that make reduced costs w + h(u) − h(v) non-negative come from min-cost-flow theory (Edmonds-Karp era) — not Johnson’s invention; his contribution is using them for APSP. 1977 · Donald B. Johnson (“Efficient algorithms for shortest paths in sparse networks,” J. ACM 24(1):1–13) composes Bellman-Ford + Dijkstra into O(V2log V + VE). not that Johnson · Donald B. Johnson (PhD Cornell 1973, founding chair of Dartmouth CS) — not David S. Johnson of “Garey & Johnson” NP-completeness fame. the payoff · on sparse graphs it beats Floyd-Warshall (dart 096) — O(VE log V) vs O(V³).
A composition, not a new primitive — which is exactly why it fits a corpus built by compounding. Donald B. Johnson, 1977
RECOMMEND FOR I-13 Bellman-Ford + Dijkstra, both landed
It composes two darts the corpus already runs — and the all-pairs distances come out with a negative edge in the mix:
Recommend:nothing new — it literally composes Bellman-Ford (dart 046, the potential + negative-cycle check) and Dijkstra (dart 055, from each vertex on the reweighted graph); the reweight w + h(u) − h(v) is pure f64 (verified A→C = −3). The distance output is a 2-D matrix (PS-004). Note: a textbook example of the campaign’s thesis — two landed features compound into a new capability with no new primitive, like Pollard p−1 (083) reusing modexp + gcd.