Bellman–Ford

The problem it solves

Dijkstra’s correctness rests on one quiet assumption: travelling further never gets cheaper. The moment an edge can be negative — a rebate, a currency conversion that profits, a cost model with credits — that assumption fails, and Dijkstra fails with it, silently, returning confident wrong numbers. Bellman–Ford is the shortest-path algorithm that survives negative edges, and beyond surviving them it performs the harder service: it detects when “shortest path” has stopped being a meaningful question, because a reachable negative cycle lets a path get cheaper forever.

The price of this generality is speed — O(V·E) against Dijkstra’s O(E log V) — and the trade is the whole story. Bellman–Ford appears wherever its two superpowers matter: currency arbitrage detection (an arbitrage is a negative cycle in log-space), difference-constraint solving, and the distance-vector routing protocols (RIP) whose routers literally run distributed Bellman–Ford against their neighbours. It also sits inside Johnson’s algorithm, re-weighting a graph once so that Dijkstra can be used safely everywhere after.

The intuition — and where it breaks down

Dijkstra is a careful planner: it commits to one node at a time, provably finished. Bellman–Ford is a flood: relax every edge in the graph, and do it V−1 times. No ordering, no priority queue, no cleverness — just the observation that if you keep offering every possible one-edge improvement, truth propagates. After the first pass, every best route of one edge is known; after the second, every best route of two edges; after k passes, k edges. Since a sensible shortest path never revisits a node, V−1 edges — hence V−1 passes — always suffice.

The intuition’s sharp edge is why revisiting never helps: a path that repeats a node contains a cycle, and detouring around a cycle only pays if the cycle’s total weight is negative. That is exactly the case where no shortest path exists at all — going around again is always cheaper, without end. So the V−1 bound and the negative-cycle test are the same insight seen from two sides, and the algorithm gets the test for free: run one extra pass, and if any edge still relaxes, some label is still falling after all legitimate path lengths are exhausted — a negative cycle is reachable, and the honest output is that fact, not a number.

Where the flood analogy misleads: it suggests all V−1 passes are always needed. In practice labels stabilise early, and a pass that changes nothing is a fixed point — every later pass would read the same labels and change nothing too. The early exit is not an optimisation garnish; on most inputs it is the difference between O(V·E) and something close to Dijkstra’s work.

Loading…

A walkthrough you can check

The default graph has edges like A→C (5), C→B (−2), A→B (6). Pass 1, in edge order: A→B relaxes B to 6; A→C relaxes C to 5; then C→B offers 5 + (−2) = 3 — B drops from 6 to 3, below a value Dijkstra might already have settled. That single moment is the entire negative-edge lesson: an “established” label undercut by a longer-but-cheaper route arriving later.

Watch two more things in the player. First, edges out of unlabelled nodes are rejected — ∞ plus anything is still ∞, and relaxing from nowhere is the classic implementation bug. Second, find the pass where the annotation reads “quiet — fixed point”: on this input it arrives well before pass V−1, and the prediction prompt asks you to justify stopping. On the negative-cycle preset, run to the end and watch the detection pass catch an edge that still relaxes — the algorithm marks the nodes it can no longer price and says so in words.

The invariant

After pass k, dist[v] is at most the weight of the cheapest path from the source to v that uses at most k edges. Induction: trivially true at k = 0 (source at 0, everything else ∞). For the step: the cheapest (k+1)-edge path to v is a cheapest k-edge path to some u plus edge u→v; by hypothesis dist[u] was already good enough when pass k+1 relaxed u→v, so dist[v] fell at least to that total. Note the inequality’s direction — labels can be better than the k-edge bound (a lucky edge order can propagate several hops in one pass) but never worse, and never below the true distance.

Two corollaries do the closing work. At k = V−1 the bound covers every simple path, so labels equal true distances — if no negative cycle is reachable. And if any edge relaxes in pass V, some label beats every simple path’s cost, which only a negative cycle can explain. Correctness and detection fall out of one invariant.

Complexity, derived

Each pass relaxes E edges at O(1) each; up to V−1 passes plus one detection pass: O(V·E) time, O(V) space for labels and parents. On the road-network-shaped graphs where Dijkstra shines, V·E is painful — a million nodes and edges means 10¹² relaxations versus Dijkstra’s ~10⁷ heap operations. That gap is why Bellman–Ford is a specialist: you pay V·E for negative edges or detection, and not otherwise.

The early exit changes the typical story: labels reachable within d edges stabilise by pass d, so the pass count tracks the graph’s “hop diameter” from the source. On shallow graphs the algorithm runs in a handful of passes; the worst case — a path graph with edges ordered adversely — genuinely needs all V−1. SPFA, a queue-based variant that only re-examines endpoints of changed labels, exploits the same fact more aggressively (and degrades to the same worst case, a fact competitive programmers learn painfully).

What people get wrong

• Relaxing from unlabelled nodes: without the base !== undefined guard, ∞ + weight overflows or, worse, compares as a real number. The rejected-edge steps in the trace exist to make this case visible.
• Skipping the detection pass: returning labels that a negative cycle has already poisoned. If negative edges are possible, the extra pass is not optional.
• Running all V−1 passes unconditionally: correct, slow, and a signal that the fixed-point insight was missed.
• Claiming Dijkstra “can be fixed” for negative edges by re-inserting nodes: the repaired algorithm is exponential in the worst case. The honest fix is this algorithm, or Johnson’s re-weighting.
• Confusing “negative edges” with “negative cycles”: negative edges are fine — that is the point. Reachable negative cycles make the question ill-posed, and the algorithm’s job is to say so.

Implementation notes

The clean loop is exactly the displayed code: for each pass, for each edge, one guarded comparison — plus changed for the early exit and one extra pass for detection. Keep parents alongside labels if you need the actual paths; to exhibit a negative cycle (arbitrage reporting needs this), take any still-relaxing edge’s head, follow parents V times to guarantee you are standing on the cycle, then walk it out.

Edge order within a pass is semantically irrelevant but practically interesting: a lucky order propagates a whole chain in one pass. Sorting edges topologically-ish (when the graph is nearly a DAG) or alternating forward/backward orders (“Yen’s trick”) halves the pass constant. For difference constraints (x_j − x_i ≤ c), build one edge per constraint plus a zero-weight source to everything: Bellman–Ford labels are then a feasible assignment, and a negative cycle certifies infeasibility — the cleanest reduction in the constraint-solving toolbox.

In routing-protocol form, each node runs the relaxation against its neighbours’ advertised labels; the famous “count to infinity” pathology of distance-vector routing is exactly a distributed negative-cycle-less version of labels chasing each other downward — worth mentioning when the interviewer asks where this algorithm lives in the real world.

The follow-up questions

Why exactly V−1 passes? A simple path has at most V−1 edges, and pass k certifies all paths of at most k edges. A path with more edges repeats a node, and the detour only pays inside a negative cycle — the case the detection pass exists to catch.

How do you list the negative cycle, not just detect it? From any edge that relaxes in the detection pass, follow parent pointers V times (you are then guaranteed inside the cycle), then walk parents until the first repeat. The nodes between repeats are the cycle.

When is Bellman–Ford preferred over Dijkstra even without negative edges? Almost never for speed — but when the graph is distributed (routing), when edges arrive as an unordered list and V is small, or as the first stage of Johnson’s algorithm to enable many Dijkstra runs afterwards.

What is SPFA and when does it help? A queue-driven Bellman–Ford that only revisits nodes whose labels changed. Excellent average case on sparse benign graphs, identical O(V·E) worst case — and famously vulnerable to adversarial inputs, which is why contest setters construct them.