Why does Bellman-Ford relax every edge V-1 times rather than once?
answer
- count edges, not vertices
- each pass extends routes one hop
- cheapest routes never revisit a vertex
- a simple route over V vertices
- V vertices allow at most V-1 edges
basics
~20 sAfter k passes over all edges, Bellman-Ford holds the best route that uses at most k edges. When no negative cycle exists, a best route never repeats a vertex, so it spans at most V-1 edges.
solid answer
~50 sOne pass over every edge extends what the algorithm knows by exactly one hop. The invariant is: after pass `k`, `dist[v]` equals the cost of the cheapest route from the source to `v` using at most `k` edges. If the graph has no negative cycle, some cheapest route to each vertex is simple — any cycle sitting on it has non-negative weight and can be cut out — and a simple route over `V` vertices uses at most `V-1` edges. So `V-1` passes are enough, and no fewer are guaranteed to be. Correctness does not depend on the order edges are scanned in; a lucky order can converge in one pass, which is why the standard early exit is legitimate: if a full pass changes nothing, the estimates are a fixed point and further passes cannot move them.
code
pseudocode · 10 lines// dist[source] = 0, dist[v] = INF for every other v
for i in 1..V-1:
changed = false
for each edge (u, v, w) in E:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pred[v] = u
changed = true
if changed == false:
breakgo deeper
Be ready to state the invariant in one line — after k passes you have the best route using at most k edges — and to explain that no shortest route repeats a vertex, so V-1 hops is the ceiling.
Explain the induction behind the invariant, why relaxation is order-independent, and why the early exit on a change-free pass is sound rather than a heuristic shortcut.
Show you know the failure direction: too few passes silently returns an over-large distance that only appears on long chains, so seed your tests with a graph whose optimum genuinely needs V-1 hops.
Own the cost argument: O(V*E) with O(V) memory, an early exit that helps typical graphs but not the bound, and a clear statement of which workloads can afford that at your graph's size.
## The state the algorithm carries Bellman-Ford solves single-source shortest paths. It keeps one number per vertex, `dist[v]`, the best route cost found so far from the source, initialised to `0` at the source and to infinity everywhere else, plus optionally `pred[v]`, the vertex you arrived from. Its only move is **relaxation** of a directed edge `(u, v)` with weight `w`: if going to `u` and then taking that edge is cheaper than the current estimate for `v`, take it. ``` if dist[u] + w < dist[v]: dist[v] = dist[u] + w pred[v] = u ``` Two properties of that move matter. First, every value in `dist` is always the cost of some **real** route, so the estimates are upper bounds that only ever fall — the algorithm is never optimistic. Second, relaxation is safe in any order; ordering affects how fast you converge, never whether the final answer is right. ## What one pass buys: exactly one more hop A *pass* means relaxing every edge in the graph once, in whatever order the edge list happens to be in. The invariant that makes the algorithm work is: > After `k` passes, for every vertex `v`, `dist[v]` is the cost of the cheapest route from the source to `v` that uses **at most k edges**. The induction is short. It is true for `k = 0`: only the source is reachable with zero edges. Suppose it holds after `k-1` passes, and let `P` be a cheapest route to `v` using at most `k` edges, whose last edge is `(u, v)`. Chopping that last edge off leaves a cheapest route to `u` using at most `k-1` edges, so `dist[u]` was already correct before pass `k` began. Pass `k` relaxes every edge, including `(u, v)`, so `dist[v]` ends the pass no worse than the cost of `P`. That is the whole idea: **passes count hops learned about, not vertices finished**. This is the point where people who learned a greedy shortest-path algorithm first go wrong — they picture each round finalising one more vertex, nearest first. Bellman-Ford finalises nothing until it stops; it just keeps pushing information one hop further out per pass. ## Why the bound is V-1 Assume the graph has no cycle of negative total weight. Then for every reachable vertex there is a cheapest route that is **simple** — it visits no vertex twice. Reason: if a cheapest route did revisit a vertex, the loop between the two visits has weight at least zero, and deleting it leaves a route that is no more expensive and shorter in hops. A simple route in a graph of `V` vertices touches at most `V` vertices and therefore uses at most `V-1` edges. Feed that into the invariant with `k = V-1` and every reachable vertex is done. The bound is tight. A straight chain of `V` vertices whose edges are listed in reverse order forces the algorithm to learn one hop per pass, using all `V-1`. ## The off-by-one, and which way it fails Stopping after `V-2` passes does not crash and does not loop; it silently returns a distance that is **too large** for any vertex whose only optimum needs exactly `V-1` edges. Because the estimates are always costs of real routes, the error is always in that direction — you get a valid but sub-optimal route, never a fantasy cheaper one. This is a nasty bug in practice: it needs a long optimal chain to show up, so small hand-written tests pass and the failure only appears on production-sized graphs. ## The legitimate early exit If a complete pass relaxes no edge at all, then no edge can ever relax again — nothing feeding it has changed — so the estimates are final and you can stop. On graphs where routes are short in hops this ends after a handful of passes. It is a real and worthwhile speedup, but it does not change the worst case: `V-1` passes over `E` edges is `O(V*E)` time, with `O(V)` space for the distance and predecessor arrays. The converse is the hook for negative-cycle work: if an edge still relaxes on a pass **after** the `V-1`th, some improving walk needs `V` or more edges, and a walk that long must repeat a vertex.
- If a full pass relaxes nothing, may you stop early — and does that change the worst case?Yes, you may stop. No edge can relax again once a whole pass changed nothing, because relaxation only fires when an endpoint's estimate has dropped; the estimates are a fixed point. It is a genuine speedup on graphs whose optimal routes are few hops deep, but the worst case is unchanged at O(V*E) — a long chain scanned in an unhelpful edge order still needs all V-1 passes.
- Does the order you iterate the edges in change the final answer?No. Relaxation is safe in any order, so the result after V-1 passes is the same for every ordering. Order changes only how fast you converge: scanning edges in the order they appear along optimal routes finishes in one pass, and in a directed acyclic graph a topological order finishes in one pass by construction. The worst-case bound assumes the least helpful order.
- What exactly goes wrong if you run only V-2 passes?A vertex whose only optimal route uses exactly V-1 edges keeps a distance that is too large — the cost of some shorter-in-hops, more expensive route. There is no error, no warning, and the answer stays a valid route, just not the cheapest. It surfaces only on graphs with long optimal chains, so small tests will not catch it.
Each pass is a round of gossip: after k rounds, everyone who is within k handshakes of the source has heard the best version of the story. With V people, no chain of fresh handshakes is longer than V-1.
saying these in an interview costs you the question
- Says V-1 is an arbitrary safety margin with no argument
- Claims a single pass over all edges is enough
- Counts passes as vertices settled, as in a greedy algorithm
- Thinks a particular edge iteration order is required for correctness
- Believes passes beyond V-1 keep lowering distances on a normal graph