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 u→vu \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.