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

The V-1 Iterations Principle

Why exactly V-1 iterations of edge relaxation guarantee shortest paths in graphs without negative cycles.

The V-1 Iterations Principle

What you'll learn: Why Bellman-Ford runs exactly V-1 iterations to guarantee correct shortest paths (when no negative cycles exist).

The Core Insight

In a graph with V vertices and no negative cycles, the longest possible shortest path between any two vertices contains at most V-1 edges. Why? Because a shortest path never repeats vertices (that would create a cycle and waste distance). Since you have V vertices total, the maximum path length is V-1 edges.

Bellman-Ford relaxes all edges in each iteration. Each iteration effectively "extends" the shortest paths discovered so far by one more edge. After iteration 1, you know all shortest paths using at most 1 edge. After iteration 2, you know all shortest paths using at most 2 edges. And so on.

The Guarantee

After V-1 iterations, you've considered paths of length up to V-1 edges—which covers every possible shortest path in the graph. No legitimate shortest path can be longer than V-1 edges without repeating vertices.

Analogy: Imagine a relay race with V checkpoints. The fastest route visits at most V-1 segments between checkpoints (you can't start and end at the same checkpoint without wasting time). After checking all V-1 possible segments, you've guaranteed you found the fastest route.

Why Not Fewer?

Some graphs require all V-1 iterations. Consider a chain: 1 → 2 → 3 → 4. Finding the shortest path from 1 to 4 requires exactly 3 iterations (V-1 where V=4) if edges are processed in unlucky order.

Key Takeaway: V-1 iterations guarantee correctness because the longest valid shortest path in a graph without negative cycles uses at most V-1 edges—one less than the number of vertices.