Why does an edge that still relaxes on Bellman-Ford's V-th pass prove a negative cycle?
answer
- what could still change after V-1 passes
- a walk longer than any simple route
- more than V-1 edges means repetition
- a repeated vertex encloses a loop
- that loop must pay you to walk it
basics
~20 sA further improvement means some cheaper walk uses V or more edges. A walk that long must repeat a vertex, and the loop it encloses can only reduce the total if its own weight is negative.
solid answer
~50 sAfter `V-1` passes every cheapest **simple** route is already found, because a simple route in a `V`-vertex graph uses at most `V-1` edges. So if one more pass over all edges still lowers some `dist[v]`, the improving walk behind it needs at least `V` edges and therefore visits some vertex twice. Cutting the loop out of that walk would give a shorter-in-hops walk that the algorithm has already priced, so the only way the longer walk can be cheaper is if the loop's total weight is below zero. One extra pass is therefore a proof, not a safety margin. Two caveats matter: it only sees negative cycles **reachable from the source**, and the affected vertices have no shortest path at all — their stored numbers are meaningless rather than minus infinity. Initialising every distance to `0` makes the check find a negative cycle anywhere in the graph.
code
pseudocode · 11 lines// runs after the V-1 relaxation passes have finished
witness = NONE
for each edge (u, v, w) in E:
if dist[u] != INF and dist[u] + w < dist[v]:
witness = v
if witness != NONE:
x = witness
for i in 1..V:
x = pred[x] // after V steps, x lies on the cycle
// follow pred from x until x recurs to list the cycle
...go deeper
Recall the rule and the reason together: one pass beyond V-1, and any edge that still relaxes means a negative cycle, because no honest route can be longer than V-1 hops.
Walk the pigeonhole argument out loud — a longer improving walk repeats a vertex, cutting the loop gives an already-priced walk, so the loop must weigh less than zero.
Show the operational side: the check only covers cycles reachable from the source, affected vertices have no answer rather than an infinite one, and you can hand back the actual loop from predecessor links.
Frame detection as a standing invariant on the data, not a debugging aid: one extra O(E) pass certifies that whatever the weights encode cannot be looped for unbounded gain, and that certificate is worth wiring into a scheduled job.
## The setup the proof leans on Bellman-Ford holds `dist[v]`, the cost of the best route to `v` found so far, and relaxes each edge `(u, v, w)` whenever `dist[u] + w < dist[v]`. After `k` full passes over the edge list, `dist[v]` is the cost of the cheapest route to `v` using at most `k` edges. In a graph with no negative cycle, some cheapest route is simple — any loop hanging off it weighs at least zero and can be excised — and a simple route in a graph of `V` vertices has at most `V-1` edges. That is why the algorithm runs `V-1` passes. ## What one more pass proves Run a further pass and suppose edge `(u, v, w)` still relaxes. Then there is a walk to `v` cheaper than anything using at most `V-1` edges, so that walk uses at least `V` edges. A walk with `V` or more edges touches `V+1` or more vertex slots in a graph with only `V` distinct vertices, so by pigeonhole it revisits some vertex — it contains a closed loop. Now remove that loop. What is left is a shorter walk to `v`, one the earlier passes already accounted for, so it costs at least as much as the current estimate. The longer walk beat that estimate, so putting the loop back **lowered** the total: the loop's weight is negative. That is a proof, not a heuristic. Equally, if the extra pass relaxes nothing, no such walk exists and every reported distance is a genuine optimum. People often describe the extra pass as "a bit of paranoia" — it is the opposite, it is the certificate the run is trustworthy. ## What the check does *not* see The algorithm only ever improves estimates that started finite, and only the source starts finite. So a negative cycle sitting in a part of the graph the source cannot reach never touches any distance, and the extra pass relaxes nothing. "No relaxation on the extra pass" therefore means **no negative cycle reachable from the source**, not "no negative cycle in the graph". If you want the stronger statement, initialise `dist[v] = 0` for *every* vertex instead of just the source. That is equivalent to bolting on a virtual source with a zero-weight edge into every vertex, which makes every vertex reachable; the distances lose their single-source meaning, but the detection pass now finds a negative cycle wherever it hides. ## What the numbers mean once a cycle exists For a vertex reachable from a negative cycle there is **no** shortest path: you can go round the loop again and again and drive the cost down without bound, so the infimum is unbounded below and no finite route attains it. Implementations do not report minus infinity — they report *that a negative cycle exists*, and if the answer matters per vertex, they mark the corrupted set: run a graph traversal forward from the cycle's vertices and flag everything reachable. Distances outside that set are still correct. ## Recovering the cycle itself Detection usually is not enough — you want the loop. Keep `pred[v]`. Take the vertex `v` that relaxed in the extra pass; it is reachable from a negative cycle but need not be on one. Walk predecessor links `V` times from it; after `V` steps you are guaranteed to have entered the cycle, because the predecessor chain eventually enters the loop and then never leaves. Record where you stand, keep following `pred` until you return to that vertex, and the vertices you passed are the cycle in reverse. ## Misreadings that cost interviews - **"A negative edge means a negative cycle."** No. A single discount edge is fine; a directed acyclic graph can be stuffed with negative edges and have perfectly well-defined shortest paths. Only a *loop* whose weights sum below zero breaks the problem. - **"Run 2V passes to be safe."** Extra passes past the detection one buy nothing. Either the `V`th pass relaxes something or the answer is final. - **"Undirected edges are the same story."** They are not. A single undirected edge with negative weight is already a negative cycle — traverse it there and back for twice its weight — so the usual formulation of this algorithm is stated for directed graphs, and an undirected graph with any negative edge has no well-defined shortest paths at all. - **"Detection is expensive."** It is one more pass: `O(E)` on top of `O(V*E)`. You essentially never skip it.
- Detection fired — how do you output the offending cycle, not just the fact of it?Keep predecessor links during relaxation. Take the vertex that relaxed on the extra pass and follow `pred` V times; the chain must have entered the cycle by then, since it eventually reaches the loop and never leaves it. Mark that vertex, keep following `pred` until you return to it, and reverse what you collected. That is the cycle, in O(V).
- What are the distances for vertices affected by a negative cycle?Meaningless. No shortest path exists for them — each extra trip round the loop is cheaper, so the cost is unbounded below and no finite route is optimal. The stored numbers are just wherever the loop happened to stop, not minus infinity. If you need per-vertex answers, traverse forward from the cycle's vertices to flag the corrupted set; distances outside it remain correct.
The extra pass is an audit, not insurance. Every honest route has already been priced, so if the books still improve, someone has found a loop that pays to walk.
saying these in an interview costs you the question
- Treats any negative edge as proof of a negative cycle
- Calls the extra pass a safety margin rather than a proof
- Assumes the check finds negative cycles anywhere in the graph
- Reports minus infinity as the distance for affected vertices
- Forgets an undirected negative edge is already a cycle