Bellman-Ford Algorithm

The Bellman-Ford algorithm finds shortest paths from one source to every other node in a weighted directed graph, even with negative edge weights. It relaxes every edge in up to V−1 passes; if a V-th pass still improves an estimate, a negative cycle is reachable from the source and no shortest path exists for the nodes it can touch.

One pass guarantees propagation by at least one more edge; favorable scan order may propagate farther, so an estimate computed early in a sweep goes stale when a later edge improves its foundation — and the next pass repairs it. That repair, not the repetition, is the mechanism to watch.

Think of each edge as a posted deal: "if you can get to B for x, I'll get you to D for x + 3." Bellman-Ford is the least clever shopper imaginable. It keeps a notebook of best-known prices, walks the entire list of deals top to bottom, updates the notebook wherever a deal beats the current entry, and then — this is the whole algorithm — walks the same list again. And again. After V−1 laps, no honest set of deals can teach it anything new.

That stubbornness is the point. Dijkstra is faster because it commits: it locks in the closest node and never looks back, which is exactly what a negative edge punishes. Bellman-Ford never commits to anything mid-run, so a cheaper route that surfaces late gets written into the notebook like any other. The Dijkstra's trap preset runs the very graph on which the Dijkstra lesson commits a wrong answer — here it comes out right. The price of that safety is honest sweat: O(V·E) instead of Dijkstra's O((V+E) log V). Use Dijkstra when all weights are non-negative; use Bellman-Ford when they aren't, or when you need to detect that "shortest" doesn't even exist.

How the Bellman-Ford Algorithm Works

The state is two maps: dist (best path cost known so far to each node — 0 for the source, ∞ for everyone else) and prev (each node's predecessor on its current best path). There is no priority queue, no visited set, no ordering cleverness of any kind. The edges sit in a plain list, in whatever order they were declared.

One pass relaxes every edge in that list, in order. Relaxing u → v with weight w asks the same question Dijkstra asks: is dist[u] + w < dist[v]? If yes, lower dist[v] and point prev[v] at u. If u is still at ∞, there is nothing to extend and the edge is skipped. That's it — many relaxations can be no-ops, especially in later passes, and watching which relaxations fire is where the understanding lives.

Why V−1 passes? Because a shortest path that visits every node uses at most V−1 edges, and one pass is only guaranteed to push correct distances one edge further along each path. After pass 1, every shortest path of one edge is settled; after pass k, every shortest path of k edges. V−1 passes cover the longest simple path a shortest route could possibly be. In practice you rarely need them all: if a pass sweeps the whole list and changes nothing, no future pass can change anything either — the inputs to every relaxation would be identical — so the algorithm stops early.

The final sweep is the verdict. After V−1 passes, every simple path has fully propagated, so nothing should improve. Run the edge list one more time: if some edge would still lower a distance, the only possible explanation is a reachable cycle whose weights sum below zero. (The sweep can only see cycles the source reaches; a negative cycle in some disconnected corner of the graph stays invisible — and harmless, since it touches no answer.) Loop it once, everything on it gets cheaper; loop it forever, costs fall without bound. "Shortest path" stops meaning anything, and the honest output is not a number but a refusal — the code returns None.

Bellman-Ford Step by Step

Run the default Propagation graph: five nodes A–E starting at A, six edges scanned in this order every pass: A→B (4), A→C (3), B→D (3), B→E (2), C→B (−2), D→E (2). One edge is negative, and the scan order hides a trap: B's outgoing edges are relaxed before the edge that improves B.

Pass 1:

1. A→B: 0 + 4 = 4 < ∞ — dist[B] = 4.
2. A→C: 0 + 3 = 3 < ∞ — dist[C] = 3.
3. B→D: 4 + 3 = 7 < ∞ — dist[D] = 7. Remember that this 7 is built on dist[B] = 4.
4. B→E: 4 + 2 = 6 < ∞ — dist[E] = 6. Same foundation, same problem.
5. C→B: 3 + (−2) = 1 < 4 — dist[B] drops to 1. The negative edge fires with zero drama: nothing was locked, so it's just another update. But D and E were priced off the old B.
6. D→E: 7 + 2 = 9 ≥ 6 — no change. Five changes this pass.

Pass 2:

1. A→B: 4 ≥ 1 — no. A→C: 3 ≥ 3 — no.
2. B→D: 1 + 3 = 4 < 7 — dist[D] drops to 4. This is the repair beat, and it is the whole lesson in one line: pass 1's answer for D wasn't wrong exactly, it was stale — computed from a value that improved later in the same sweep. In this scan order B’s outgoing edges had already been examined, so D had to wait a lap.
3. B→E: 1 + 2 = 3 < 6 — dist[E] drops to 3, the same repair.
4. C→B and D→E: no change. Two changes this pass.

Pass 3: all six edges sweep through without a single change — which is a proof, not a formality. Distances are stable; passes 4 and beyond are skipped.

Check sweep: one more lap over all six edges, looking for trouble. Nothing improves, so there is no negative cycle and the answer stands: A=0, B=1, C=3, D=4, E=3.

On the canvas the same story reads at a glance: no node turns green mid-run — everything stays amber-tentative until the run ends and all five lock together. The bottom strip shows the fixed edge list with a cursor sweeping it, pass after pass; the only thing that ever moves is the cursor, because Bellman-Ford never chooses. Now switch to the Negative cycle preset and watch the same machinery refuse: B→C→D→B sums to −1, dist[B] falls by one every pass (0, then −1, then −2 at the end of each pass; the first A→B relaxation sets 1 before D→B lowers it in the same sweep), and the check sweep catches the cycle still improving — the loop lights up red and the run ends with no answer. (The red loop is traced from the algorithm's own prev pointers, not annotated by hand.)

Time and Space Complexity

Each pass touches all E edges at O(1) apiece, and there are at most V−1 passes plus the detection sweep. The early exit makes the best case a single productive pass plus one empty confirming pass — O(E). Space is just the dist and prev maps; there is no queue to grow. Compare Dijkstra's O((V+E) log V): on a graph with all-non-negative weights and no need for cycle detection, Dijkstra usually provides a better worst-case time bound for the same answer.

Edge Cases

• Negative edge weights. The headline: handled correctly, no special casing. An edge with dist[u] = ∞ contributes nothing; a negative edge lowering a finite estimate is an ordinary update.
• Negative cycles. Detected, not survived. Any node on the cycle — or downstream of it — has no well-defined shortest distance, and the check sweep is what catches it. Skipping that sweep means silently returning garbage.
• Unreachable nodes. Never receive a finite distance; every edge out of them is skipped (u not yet reached), and they finish at ∞.
• Edge scan order. Changes how many passes convergence takes — a lucky order can settle everything in one pass, an adversarial one needs all V−1 — but never changes the final distances. The bound holds for any order.
• Single node, no edges. Zero-iteration passes, an empty check sweep, and the correct answer: dist[source] = 0.

Common Mistakes

1. Skipping the ∞ guard. Relaxing an edge whose source is unreached must be a no-op. In languages where ∞ is a real float this works by accident; with integer sentinels (INT_MAX + w overflows) or missing-key semantics it corrupts the run. The displayed code's u in dist check is load-bearing.
2. Declaring distances final after one pass. Pass 1 of the default graph reports dist[D] = 7; the truth is 4. A value in the notebook is an estimate until a full pass changes nothing — that is the entire reason the outer loop exists.
3. Detecting cycles too early. An improvement in pass 3 of 4 is normal propagation, not a negative cycle. The inference "still improving ⇒ cycle" is only valid after all V−1 passes have run.
4. Running V passes instead of V−1, or stopping at V−2. Off-by-one in the pass count either wastes a sweep or leaves the longest paths one hop short of correct. V−1 is exact: the longest simple path has V−1 edges.
5. Reaching for Bellman-Ford when Dijkstra applies. If every weight is non-negative and you don't need cycle detection, the O(V·E) is pure overpayment. Bellman-Ford's niche is negative edges, cycle detection, and settings like distributed routing where "relax everything, repeatedly" is the only move available.