Bellman-Ford and Negative Edges
What This Concept Is
Bellman–Ford repeatedly relaxes all edges from currently finite labels. A snapshot DP version uses the previous round exclusively: after k rounds it gives the optimum over walks using at most k edges. The usual in-place implementation can propagate through several edges in one pass, so that exact bounded-edge invariant does not describe its intermediate values.
For in-place passes, labels remain costs of discovered walks and after k full passes are no greater than the optimum over walks of at most k edges. Without reachable negative cycles, V-1 passes suffice because an optimal simple path exists with at most V-1 edges.
Why It Matters Here
Getting the invariant right prevents incorrect traces and stopping rules. Negative-cycle reporting also needs scope: only descendants of a source-reachable negative cycle have unbounded-below costs. Other reachable vertices can remain finite and disconnected cycles do not affect this source.
Concrete Examples
Process 0→1:1 then 1→2:1 in that order. An in-place first pass sets distance 2 to 2, already using two edges. A snapshot first round leaves 2 unreachable. Both can be correct implementations of different round semantics.
After V-1 passes, scan edges for further improvements from finite tails. Seed the improving heads and traverse outgoing edges to mark all affected descendants. Return -infinity for those vertices, None for unreachable vertices and ordinary integers elsewhere. Clearing affected parent pointers prevents presenting a finite path as an optimum where no finite optimum exists.
Common Confusion / Misconceptions
A global negative-cycle flag is weaker than per-target classification. Starting all labels at zero instead of only the chosen source detects cycles anywhere, which is useful for a different contract. A fixed large sentinel may be overflowed or exceeded by legitimate costs; use an explicit unreachable value and guard relaxation. Queue-based variants need their own analysis and can still be slow.
How To Use It
Explain why a full pass without changes permits early exit: every reachable edge already satisfies its relaxation inequality. If a negative cycle were reachable with finite stable labels, summing inequalities around it would give a contradiction. The lab includes O(V+E) postprocessing for affected vertices and uses O(V+VE+E) time overall, including initialization and validation.
Check Yourself
- Why can one in-place pass traverse multiple edges?
- Why are only finite-tail improvements relevant to this source?
- Why must affected status propagate beyond the cycle itself?
- What changes when every vertex starts at distance zero?
Mini Drill or Application
Trace snapshot and in-place passes on the two-edge chain. Then use the six-vertex negative-cycle fixture and classify every target separately. Produce a finite parent path for the unaffected branch and explain why no finite optimum witness can be returned for affected vertices. See P11.
Read This Only If Stuck
Find Bellman–Ford invariants and negative-cycle reachability in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.