THE FOLD / CO-OP / THE BROADCAST / THE JOHNSON APSP
THE JOHNSON APSP
all-pairs shortest paths with negative edges, via reweighting
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Johnson’s algorithm finds all-pairs shortest paths even with negative edge weights — which Dijkstra alone cannot handle. It runs one Bellman–Ford pass to compute a potential h(v) at each node, reweights every edge to w′(u,v) = w(u,v) + h(u) − h(v) — now all non-negative, and with the same shortest paths — then runs fast Dijkstra from every source, undoing the shift at the end.
LIT verified live: over 100 random graphs with negative edges (no negative cycle) Johnson’s distances match Floyd–Warshall exactly (window.__johnson). FIG no framing; exact.
LIT verified live: over 100 random graphs with negative edges (no negative cycle) Johnson’s distances match Floyd–Warshall exactly (window.__johnson). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-broadcast — the routing tables broadcast across a network, every node’s shortest distance to every other, computed even when some links have negative cost. Johnson is that routing solve. AVAN (AI) built the instrument: the Bellman–Ford potentials, the edge reweighting, the per-source Dijkstra, the Floyd–Warshall cross-check.
Credit as content: Donald Johnson (1977). The weave: David names the broadcast; I shift the weights by a potential to remove the negatives, run Dijkstra everywhere, and confirm the distances match the exhaustive all-pairs solve.
Credit as content: Donald Johnson (1977). The weave: David names the broadcast; I shift the weights by a potential to remove the negatives, run Dijkstra everywhere, and confirm the distances match the exhaustive all-pairs solve.
3 ONE DIMENSION
Reweighting: w′(u,v) = w(u,v) + h(u) − h(v). Along any path the h-terms telescope, so path lengths shift by the same constant — the shortest path is unchanged, but every edge is now ≥ 0.
4 TWO DIMENSIONS · INTERACTIVE
A weighted graph with negative edges; Johnson’s all-pairs distances (from a chosen source) are shown against Floyd–Warshall.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the reweighted non-negative graph on which Dijkstra runs.
AVAN’s addition (the inverse-companion): reweight the edges with node potentials (from one Bellman–Ford) so every weight becomes non-negative without changing which paths are shortest — then Dijkstra runs from every source, fast, even on a graph that had negative edges. The inverse of ‘Dijkstra forbids negative edges’ is ‘shift the weights by a potential to remove the negatives, preserving shortest paths.’ Magenta is the negative edges that block Dijkstra; green is the reweighted non-negative graph. A gauge transformation on edge weights. (Kin to the-bellman-ford.)
LIT Genuine Johnson's algorithm (Johnson 1977). Verified live: the Bellman-Ford potentials + edge reweighting + per-source Dijkstra reproduce the Floyd-Warshall all-pairs distances exactly for 100 random graphs containing negative edges but no negative cycle (window.__johnson.matchesFloyd).
FIG No framing: the Bellman-Ford potentials, the edge reweighting, the per-source Dijkstra, and the Floyd-Warshall cross-check run in-browser and agree exactly. The AVAN inverse is honest — node potentials shift edge weights non-negative without changing which paths are shortest (the h-terms telescope), so Dijkstra runs everywhere; magenta is the negative edges that block Dijkstra, green the reweighted non-negative graph. A gauge transformation. Kin to the-bellman-ford.
FIG No framing: the Bellman-Ford potentials, the edge reweighting, the per-source Dijkstra, and the Floyd-Warshall cross-check run in-browser and agree exactly. The AVAN inverse is honest — node potentials shift edge weights non-negative without changing which paths are shortest (the h-terms telescope), so Dijkstra runs everywhere; magenta is the negative edges that block Dijkstra, green the reweighted non-negative graph. A gauge transformation. Kin to the-bellman-ford.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BROADCAST · David Lee Wise (ROOT0), with AVAN