Detecting Negative Weight Cycles
What you'll learn: How to use Bellman-Ford's final V-th iteration to catch graphs containing negative weight cycles.
Why Detection Matters
You've learned that Bellman-Ford runs V-1 iterations to find shortest paths. But what if a negative weight cycle exists? In that case, there is no shortest path—you can keep looping through the cycle, making distances arbitrarily small. Bellman-Ford can detect this problem with one extra iteration.
The V-th Iteration Trick
After completing V-1 iterations, all shortest paths should be finalized (assuming no negative cycles). Here's the clever insight: if you can still relax any edge in a V-th iteration, a negative cycle must exist.
Think of it like this: you've already "settled" all distances after V-1 rounds. If an edge still offers an improvement, it means you're benefiting from a cycle that reduces total weight—a negative cycle. You're essentially circling back and finding cheaper paths when there shouldn't be any left.
How It Works
After your V-1 standard iterations:
- Run one more pass through all edges
- Try to relax each edge as usual
- If any edge successfully relaxes, flag that a negative cycle exists
- If no edges relax, the shortest paths are valid
This is often called the "detection pass" or "verification step."
Practical Consequence
If you detect a negative cycle, you typically cannot report meaningful shortest paths from the source to vertices affected by the cycle (their distances would be -∞). Some implementations mark these vertices specially or return an error condition.
Key Takeaway: A V-th iteration in Bellman-Ford acts as a negative cycle detector—if any edge still relaxes after V-1 iterations, a negative weight cycle exists in the graph.