Relax (u, v)
if d[u] + w < d[v] then d[v] = d[u] + w
The update rule.
In Dijkstra's algorithm, relaxing an edge of weight updates the tentative distance: . The vertex with the smallest tentative distance is finalised next.
This page is easier if you are comfortable with:
Start with and all others infinite. For the edge of weight 4: . Then with weight 2 gives ; relaxing with weight 1 gives , a better route via . If , and : , so there is no update.
The algorithm repeatedly picks the unfinalised vertex of least distance and relaxes its outgoing edges. It is correct for non-negative weights because a finalised distance can never be improved. The idea is that a shortest path to ends with some edge preceded by a shortest path to , which is the principle behind the all-pairs recurrence of Floyd–Warshall.
With a simple array the running time is ; with a priority queue, . Related problems are the minimum spanning tree (minimum spanning tree size), maximum flow (max-flow min-cut) and the route inspection problem (route inspection); bounds for the travelling salesperson use shortest paths (travelling salesperson bounds).
Relaxation improves a distance estimate whenever a shorter route is found.
The route A → C → B (2 + 1) beats the direct edge of weight 4.
These examples are worked by hand, step by step, so you can compare your own working.
Relax (weight 4) with , .
Relax (weight 1) with , .
Relax with , , .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
if d[u] + w < d[v] then d[v] = d[u] + w
The update rule.
new d[v] = 7
4 + 3 < 9.
d[v] stays 5
7 > 5.
d[v] = ∞ becomes d[u] + w
First visit.
Dijkstra’s algorithm repeatedly picks the unvisited vertex u with smallest tentative distance and relaxes each edge (u, v) of weight w: d[v] ← min(d[v], d[u] + w).
d[u] = 4, w(u, v) = 3, d[v] = 9. Update d[v].
d[u] = 4, w = 3, d[v] = 5. Update d[v].
Source s: d[s] = 0, edges s→a (2), s→b (7), a→b (3). Find d[b].
How many relaxations does Dijkstra do on a graph with 10 edges?
works with negative edges ✗
requires non-negative weights ✓
Use Bellman–Ford otherwise.
always set d[v] = d[u] + w ✗
only if smaller ✓
Use min.
arbitrary order ✗
smallest tentative distance ✓
Greedy choice.
initial 0 ✗
initial ∞ except the source ✓
Unknown distances.
Try each one on paper, then open the answer. Use the solver above to see the full working.
9
8
5
5
5
16
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Updating d[v] if a shorter route via u exists.
d[v] = min(d[v], d[u] + w).
No.
The unvisited vertex with smallest d.
Floyd–Warshall recurrence.
minimum spanning tree size.
More in Discrete maths and number theory and the formula sheets.