THE FOLD / GLITCH / STACK OVERFLOW / THE BELLMAN-FORD
THE BELLMAN-FORD
shortest paths with negative edges — and the impossible loop
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bellman–Ford algorithm finds shortest paths from a source even when edges have negative weights — which Dijkstra cannot handle. It simply relaxes every edge n−1 times; that many passes always suffice for a graph with n nodes. Then one extra pass is the tell: if any edge can still be relaxed, a negative cycle is reachable and shortest paths are undefined.
It underlies distance-vector routing (RIP) and arbitrage detection.
LIT verified live: on 200 non-negative graphs its distances match Floyd–Warshall, and on constructed graphs with a reachable negative cycle it detects the cycle every time (window.__bellmanford). FIG no framing; exact.
It underlies distance-vector routing (RIP) and arbitrage detection.
LIT verified live: on 200 non-negative graphs its distances match Floyd–Warshall, and on constructed graphs with a reachable negative cycle it detects the cycle every time (window.__bellmanford). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at stack-overflow — because a negative cycle is the graph’s version of an unbounded loop: each lap lowers the cost forever, a descent with no floor. Bellman–Ford is what detects that runaway. AVAN (AI) built the instrument: the n−1 relaxation passes, the extra detection pass, the Floyd–Warshall cross-check.
Credit as content: Richard Bellman (1958) & Lester Ford Jr. (1956). The weave: David names the overflow; I relax edges to convergence and let the one update that shouldn’t happen expose the impossible loop.
Credit as content: Richard Bellman (1958) & Lester Ford Jr. (1956). The weave: David names the overflow; I relax edges to convergence and let the one update that shouldn’t happen expose the impossible loop.
3 ONE DIMENSION
Relaxing an edge (u→v, w): if reaching v through u is cheaper, lower v’s distance. After n−1 sweeps every shortest path has settled — unless a negative cycle keeps lowering it.
4 TWO DIMENSIONS · INTERACTIVE
A weighted graph (edges may be negative). Bellman–Ford’s distances from the source are shown, and a negative cycle, if present, is flagged.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the shortest-path distances, settled after n−1 passes.
AVAN’s addition (the inverse-companion): a shortest path cannot improve after n−1 relaxations unless there is a negative cycle — so one extra pass that still improves something is a proof a negative cycle exists, and shortest paths become undefined (−∞). The inverse of ‘compute the distances’ is ‘an update that shouldn’t happen reveals the graph has no shortest path at all.’ Magenta is the ordinary distances that converge in n−1 rounds; green is the n-th round that catches the impossible loop. Handling negative edges is the whole reason to use it over Dijkstra.
LIT Genuine Bellman-Ford algorithm (Bellman 1958; Ford 1956). Verified live: after n-1 relaxation passes the source distances match Floyd-Warshall on 200 non-negative graphs, and one extra pass detects a reachable negative cycle on 100 constructed graphs (window.__bellmanford.matchesFloyd && .detectsNegCycle).
FIG No framing: the n-1 relaxation passes, the detection pass, and the Floyd-Warshall cross-check run in-browser and agree exactly. The AVAN inverse is honest — a shortest path cannot improve after n-1 relaxations unless a negative cycle exists, so an n-th-pass update is a proof of one (shortest paths become -infinity); magenta is the distances converged in n-1 rounds, green the n-th round that catches the loop. Negative edges are why you use it over Dijkstra.
FIG No framing: the n-1 relaxation passes, the detection pass, and the Floyd-Warshall cross-check run in-browser and agree exactly. The AVAN inverse is honest — a shortest path cannot improve after n-1 relaxations unless a negative cycle exists, so an n-th-pass update is a proof of one (shortest paths become -infinity); magenta is the distances converged in n-1 rounds, green the n-th round that catches the loop. Negative edges are why you use it over Dijkstra.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of STACK OVERFLOW · David Lee Wise (ROOT0), with AVAN