---
title: "Bellman-Ford"
description: "Relax every edge V−1 times — handles negative weights, detects negative cycles"
source: https://vizlearn.app/algorithms/graph/bellman-ford
access: premium (interactive player requires Lifetime; this doc is free)
---

# 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

| Case | Time | Space |
|---|---|---|
| Worst (full V−1 passes) | O(V · E) | O(V) |
| Best (converges in one pass, early exit) | O(E) | O(V) |

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.