◄ WORLD V · SONNY 5DART 046 · a helldive at the net

BELLMAN–FORD relax, repeat, settle

Find the shortest route through a network by a stubbornly simple idea: for every edge, ask “is it cheaper to reach the far end through this edge?” and if so, lower the cost. Do that to every edge, over and over, and the distances settle to the true shortest paths — even with negative edges, where the famous Dijkstra fails. Two names on it; four people found it. It runs in real I-13 on the new array.

THE TECHNIQUE one operation, repeated: edge relaxation

Keep a distance to each node, all infinite but the start. For each edge (u→v, weight w): if dist[u] + w < dist[v], improve dist[v]. Sweep all edges V−1 times and every distance is correct. Watch the numbers fall. live demo

HISTORY & CREDIT two names, four discoverers

“Bellman–Ford” sounds like two collaborators; they never worked together, and two more people got there first-ish. cited

1955 · Alfonso Shimbel gives the method — arguably the earliest.
1956 · Lester Ford Jr. publishes it (RAND).
1959 · Edward F. Moore gives the breadth-first variant (“Moore’s algorithm”; presented 1957, published 1959), still used for routing.
1958 · Richard Bellman — who coined “dynamic programming” — publishes it and lends the recurrence its fame.
vs Dijkstra · slower than Dijkstra, but it handles negative-weight edges and detects negative cycles — the reason it survives.

Some call it Bellman–Ford–Moore; the honest name has at least four. shared

RECOMMEND FOR I-13 a no-wall over the array

Relaxation is one comparison and one indexed write — the array carries the distances, threaded through the sweeps. It runs:

def relax(I d, I u, I v, I w) { if d[u] + w < d[v] { d[v] <- d[u] + w -> d } -> d }
$ i13 run bf.i13 # edges 0->1(4), 0->2(1), 2->1(1), 1->3(1) distB = 2 # 0->2->1 (1+1) beats 0->1 (4) distD = 3 # 0->2->1->3
Recommend: nothing new — a clean no-wall on the bounded array, and a fitting one: Bellman–Ford is dynamic programming over a table, and the array is exactly the table. The whole method is edge relaxation folded over the distance array — bounded recursion carrying an aggregate, which is now native.
Note: the array made the DP table expressible; the fold was always I-13’s shape. Graph algorithms in general want an adjacency structure, but for a fixed edge list the bounded array is enough.