Programming

Bellman–Ford

It is not a slower Dijkstra for broken edges. It is a deflationary gravity: a monotone operator pressing down on every road simultaneously until distances freeze into their least fixed point—or spiral endlessly into a negative abyss.

Dijkstra freezes T at 12; relax all edges across 4 rounds to uncover the -11 siphon.

Mission 04about 9 min

Drive distance vectors to their tropical fixed point and catch negative runaway cycles before they corrupt routing.

  1. Relax every edge across sequential rounds to lower tentative labels
  2. Witness round four certify equilibrium or flag an active siphon
  3. Trace the min-plus semiring matrix to observe tropical deflation

After thisYou can route networks with negative edge weights and trap arbitrage cycles in polynomial time.

Short on timeThe GraphCanvas relaxation panel in §1

A Universe Falling Into Equilibrium

3 minthe hook

A negative cycle is a currency loop that pays 11 on every lap, and no number of relaxations will settle it. Without one, 3 rounds lower the labels on this board, and the 4th certifies the freeze.

The board holds five towns, six one-way roads, and one negative edge that closes no loop. Call the picture the snowfield: each round lowers every point to the lowest height its neighbours allow, and a negative cycle is a hole with no floor.

Before you touch the transport, commit to a prediction below.

1 / 6
Bellman–Ford · source S · directed
-483145SPQRT

1/6 start at S: d = 0, others ∞; 4 rounds of full relaxation

nodeSPQRT
d0∞∞∞∞
  1. 1 start at S: d = 0, others ∞; 4 rounds of full relaxation

Six one-way roads and their weights. The negative edge R→T = −4 has no cycle through it, so this graph has a well-defined answer. Step through and watch the d row.

Watch the distance row: it only falls, and the round that changes nothing is the certificate that the snowfield has settled.

The edge list is written back-to-front on purpose. Scanning it in this reverse order advances the wavefront by exactly one hop per round, making the round count visible.

The distance vector under the graph holds one number per town. Each round replaces every label with the best route over its incoming roads, and no number ever rises.

Start with S at 0 and every other town at ∞. For 5 vertices, the theoretical guarantee is at most 4 rounds. How many rounds actually lower some distance before the table freezes?

NextWhy does Dijkstra's greedy stamp freeze incorrect distances under negative edges?

The Failure of Dijkstra’s Horizon

2 minthe trap

Dijkstra assumes that any prefix of a shortest path must itself be a shortest path. A single negative edge shatters that foundation: a town settled early with a low score can later be undercut by a longer detour that gains time.

Standard curricula frame Bellman–Ford as a sluggish fallback that repeatedly relaxes every edge until nothing changes. That framing hides the real mathematical object.

The repeated passes are not crude brute force. They are successive iterations of a monotone contracting operator converging to its least fixed point.

NextHow does the deflationary dynamic-programming operator relax edges in waves?

The Deflationary Operator

2 minthe invariant

The state consists of a single vector , pinned at . Between rounds, nothing else is stored.

The final vector satisfies Bellman’s equation for the principle of optimality (Bellman 1958):

Define the relaxation operator by testing every incoming road against the current estimate:

Then means no road can be relaxed, and one round of Bellman–Ford is one application of . The operator possesses two essential properties:

  • Monotone. If entrywise, then . Minimums and additions preserve order.
  • Deflationary. for every vector . Each step either reduces a distance estimate or leaves it unchanged; a label never rises.

Because is deflationary, distance estimates descend monotonically from and can never fall beneath the true shortest paths. When a round produces no change, , certifying that the vector has reached its least fixed point.

NextWhat happens when an authorized transaction enters a negative-cost cycle?

The Finite Horizon and the Negative Abyss

2 minthe algebra

Start at with source at and all other entries at . The sequence drops monotonically until it stabilizes.

Theorem (Shimbel 1955; Bellman 1958). If no negative cycle is reachable from source , then is the exact shortest-path vector. Any subsequent round changes nothing.

The proof is a cycle-elimination argument. Any walk that visits more than edges must repeat a vertex, forming a cycle. Because no reachable cycle has negative weight, excising that cycle cannot increase total cost.

Therefore, an optimal walk without cycles exists, containing at most edges. Each application of extends optimal paths by at least one edge, guaranteeing convergence within passes.

Tropical Matrix Powers

Let be the adjacency matrix with and otherwise. Under tropical operations and , the -th power measures exact path lengths:

where has on the diagonal and off it. One Bellman–Ford round is the tropical affine mapping . After rounds, the vector matches row of the partial closure .

The complete sum is the min-plus matrix closure. It satisfies and stabilizes at because simple paths have length at most .

for k = 1 … n
  for i = 1 … n
    for j = 1 … n
      R[i][j] ← R[i][j] ⊕ R[i][k] ⊗ R[k][j]
semiring (min, +)⊕ = min, ⊗ = +zero +∞one 0
S
P
Q
R
T
S
0
4
5
7
3
P
∞
0
∞
3
-1
Q
∞
1
0
4
0
R
∞
∞
∞
0
-4
T
∞
∞
∞
∞
0

All-pairs closure under (min, +): R after n = 5 rounds.

The same six roads as a min-plus matrix. The reflexivity the panel adds on the diagonal is the L^(0) = I term. Drag the slider and read row S: it finishes at 0, 4, 5, 7, 3, the distances the canvas reaches.

The matrix panel uses a different scheduling order than Bellman–Ford. It computes the triple loop over intermediate vertices, whereas Bellman–Ford iterates over edge relaxations. Both converge to the identical fixed point because both compute the same algebraic closure.

The n-th Round: Detecting the Abyss

Run one round past . The test asks if any road still satisfies .

If a label still drops, a walk with edges beats every shorter walk. Stripping cycles from that walk cannot increase weight unless the cycle itself has strictly negative weight (Ford 1956; Bellman 1958).

When a negative cycle is reachable, no finite fixed point exists. Each lap around the cycle subtracts energy, driving distances toward . The -th round fires an alarm precisely because the fixed point has vanished.

Add road T→P with weight −10 to the picture. Now P→R→T→P is a cycle of total weight , and every lap removes 11 from the labels it touches.

1 / 6
Bellman–Ford · source S · directed
-10-483145SPQRT

1/6 start at S: d = 0, others ∞; 4 rounds of full relaxation

nodeSPQRT
d0∞∞∞∞
  1. 1 start at S: d = 0, others ∞; 4 rounds of full relaxation

The same five towns plus T→P = −10. The cycle P→R→T→P weighs −11, so the labels keep falling and the test round flags a reachable negative cycle.

1 minboss round

Add road T→P = -10 to close the cycle P→R→T→P. What happens on the n-th round of relaxation?

NextHow do distributed distance-vector routers detect arbitrary currency loops?

Distance Vectors and Currency Arbitrage

2 minthe simulation

Distance-vector routing protocols such as RIP implement Bellman–Ford across physical networks. Each router broadcasts its vector of distances to immediate neighbours, updating local routing tables according to the Bellman equation.

The infamous ‘count-to-infinity’ failure mode occurs when a link breaks and routers bounce obsolete distances back and forth. This is the physical realization of a missing fixed point, requiring split-horizon rules and hop-count limits.

Currency arbitrage is the exact inverse application. Set edge weights to so that multiplying currency conversions corresponds to summing weights. A profitable round trip becomes a negative cycle, transforming the -th round test into an arbitrage detector.

Next missionQuicksortA naive pivot burns 5×10^9 comparisons on sorted input; partition around pivots to sort in 2M steps.

Moore’s Queue: Chasing the Active Frontier

Relaxing all edges in every round costs operations. Moore (1959) introduced the Shortest Path Faster Algorithm (SPFA), keeping a queue of vertices whose distances recently decreased.

Only edges leaving active vertices are relaxed. While worst-case complexity remains , typical execution speeds rival Dijkstra on sparse graphs.

Attributions

  • Shimbel 1955 — Structural determination of the shortest route matrix: the round-robin relaxation and its bound, the earliest form of the method.
  • Bellman 1958 — On a routing problem: the principle of optimality framing, the Bellman equation , and the iteration bound.
  • Ford 1956 — Network flow theory, RAND report P-923: the edge-list, label-correcting version and its use in flow problems.
  • Moore 1959 — The shortest path through a maze: the queue-based refinement of section 5, found independently.
  • Tarski 1955 — the lattice fixed-point theorem behind “a monotone iteration from the top settles at a fixed point”.
  • Schrijver 2005 — On the history of the shortest path problem: the source for the priority of the 1955–1959 attributions above.