Edge Relaxation in Bellman-Ford
What you'll learn: How the Bellman-Ford algorithm systematically improves shortest path estimates by relaxing every edge in the graph, repeatedly.
The Core Idea
In Bellman-Ford, edge relaxation is the fundamental operation that gradually discovers shorter paths. Unlike Dijkstra's algorithm (which carefully selects which edges to relax based on a priority queue), Bellman-Ford takes a simpler approach: it relaxes every single edge in the graph, and it does this repeatedly for V-1 iterations (where V is the number of vertices).
How It Works
Each relaxation asks: "If I've found a path to vertex u with distance dist[u], and there's an edge from u to v with weight w, can I reach v faster by going through u?"
The relaxation operation checks:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
Why Relax All Edges V-1 Times?
Think of it like spreading news through a network where each person can only tell their direct neighbors once per day. After one day, the news reaches everyone one hop away. After two days, it reaches everyone two hops away. In the worst case (a chain of V vertices), it takes V-1 days for news to reach the farthest person.
Similarly, after k iterations of relaxing all edges, Bellman-Ford has correctly computed shortest paths using at most k edges. Since any shortest path in a graph without cycles uses at most V-1 edges, V-1 iterations guarantee correctness.
Key Takeaway: Bellman-Ford relaxes every edge V-1 times, allowing shortest path estimates to "propagate" through the graph one edge at a time, eventually finding all shortest paths regardless of edge order.