Dijkstra Relaxation Step Explained with Worked Examples

In Dijkstra's algorithm, relaxing an edge of weight updates the tentative distance: . The vertex with the smallest tentative distance is finalised next.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

  • weighted graphs
  • shortest paths
  • comparing tentative distances

What Dijkstra relaxation step means

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).

What is it used for?

Relaxation improves a distance estimate whenever a shorter route is found.

How to use dijkstra relaxation step

  1. Set , all others .
  2. Pick the unfinalised vertex with the smallest .
  3. For each edge set .
  4. Repeat until all vertices are finalised.

Graph

Tentative distance to B before and after relaxing via Cbefore: 4after: 300.511.522.53012345Tentative distance to B before and after relaxing via CstageyGraph with x from 0 to 3 and y from 0 to 5. Shows bars (2); point before: 4 at (1, 4); point after: 3 at (2, 3).

The route A → C → B (2 + 1) beats the direct edge of weight 4.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: first relaxation

Relax (weight 4) with , .

Worked example
Answer
44
  1. Formula

Example 2: a better route

Relax (weight 1) with , .

Worked example
Answer
33
  1. Formula

Example 3: no update

Relax with , , .

Worked example
Answer
77
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Relax (u, v)

if d[u] + w < d[v] then d[v] = d[u] + w

The update rule.

d[u] = 4, w = 3, d[v] = 9

new d[v] = 7

4 + 3 < 9.

d[u] = 4, w = 3, d[v] = 5

d[v] stays 5

7 > 5.

From ∞

d[v] = ∞ becomes d[u] + w

First visit.

Word problems

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).

An improvement

d[u] = 4, w(u, v) = 3, d[v] = 9. Update d[v].

  1. d[u] + w7
  2. Compare7 < 9
  3. Check: d[v] = 7 ✓7.

No improvement

d[u] = 4, w = 3, d[v] = 5. Update d[v].

  1. 7 > 5
  2. Check: unchanged ✓5.

A sequence Higher

Source s: d[s] = 0, edges s→a (2), s→b (7), a→b (3). Find d[b].

  1. Direct7
  2. Via a2 + 3 = 5
  3. Check: 5 ✓5.

Counting Higher

How many relaxations does Dijkstra do on a graph with 10 edges?

  1. Each edge once
  2. Check: ✓10.

Common mistakes

Negative weights

works with negative edges ✗

requires non-negative weights ✓

Use Bellman–Ford otherwise.

Updating when not smaller

always set d[v] = d[u] + w ✗

only if smaller ✓

Use min.

Picking any vertex

arbitrary order ✗

smallest tentative distance ✓

Greedy choice.

Forgetting ∞

initial 0 ✗

initial ∞ except the source ✓

Unknown distances.

Exam tips

  1. d[v] ← min(d[v], d[u] + w).
  2. Smallest unvisited first.
  3. Non-negative weights.
  4. Start d[s] = 0.
  5. Track predecessors.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. min(10, 6 + 3) Foundation

9

2. min(8, 6 + 3) Foundation

8

3. d[u] = 0, w = 5: new d[v] from ∞ Foundation

5

4. Path s→a→b: 2 + 3 Higher

5

5. min(7, 2 + 3) Higher

5

6. d[u] + w = 12 + 4 Higher

16

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Dijkstra’s algorithm
Shortest paths from a source.
Relaxation
Updating a distance.
Tentative distance
Current best estimate.
Edge weight
Cost of an edge.
Predecessor
Previous vertex on the path.
Greedy algorithm
Chooses the locally best option.

Frequently asked questions

What is relaxation?

Updating d[v] if a shorter route via u exists.

What is the update rule?

d[v] = min(d[v], d[u] + w).

Does Dijkstra allow negative weights?

No.

Which vertex is chosen next?

The unvisited vertex with smallest d.

Which page covers Floyd–Warshall?

Floyd–Warshall recurrence.

Which page covers minimum spanning trees?

minimum spanning tree size.

More in Discrete maths and number theory and the formula sheets.