Course contentsShow
← Computer Science
Lesson 985 of 2,87223. Shortest Path AlgorithmsFree lesson

Detecting Negative Weight Cycles

Using a final V-th iteration to detect if negative cycles exist in the graph.

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:

  1. Run one more pass through all edges
  2. Try to relax each edge as usual
  3. If any edge successfully relaxes, flag that a negative cycle exists
  4. 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.