Graph Theory37 sections · 1633 units
Open in Course

The Relaxation Operation

(Core building block)

Relaxation checks if you can improve the distance to node vv by going through edge uvu \to v. The condition is: if dist[u] + weight(u, v) < dist[v], update dist[v] to the better value. This operation is the same in both Dijkstra and Bellman-Ford. The difference is how many times and in what order you relax edges. Dijkstra relaxes each edge once in priority order.

Bellman-Ford relaxes all edges multiple times. The power of relaxation is that it propagates distance improvements. If you improve dist[u], then all edges from uu might lead to improvements in their destinations. Repeated relaxation ensures these improvements reach all nodes.