Dijkstra's algorithm

Algorithms on graphs

A-level Further Maths (9FM0) · Decision 1

ORIGINAL

Order of labelling, final values, working values — then trace the route back from the destination.

Board and spec code confirmed against Edexcel 9FM0 · registry checked 2026-07-17How this checking works

Question

A network has vertices

A, B, C, D, E, F

and weighted edges

AB = 4

AC = 2

BC = 1

BD = 5

CD = 8

CE = 10

DE = 2

DF = 6

EF = 3

. Use Dijkstra's algorithm to find the shortest route from

A

F

and state its length.

Every step worked, with the reasoning.

1
Label $A$ : order 1, final value $0$ . Working values: $B = 4$ , $C = 2$ .
Start at $A$ ; each vertex joined directly to it gets a working value equal to the edge weight.
2
Label $C$ : order 2, final value $2$ . Update $B = \min(4,\ 2 + 1) = 3$ , $D = 2 + 8 = 10$ , $E = 2 + 10 = 12$ .
Make the smallest working value permanent, then replace a neighbour's working value only if the new route is shorter.
3
Label $B$ : order 3, final value $3$ . Update $D = \min(10,\ 3 + 5) = 8$ .
$B$ now has the smallest working value; its only unlabelled neighbour is $D$ .
4
Label $D$ : order 4, final value $8$ . Update $E = \min(12,\ 8 + 2) = 10$ , $F = 8 + 6 = 14$ .
Both of $D$ 's unlabelled neighbours get new working values.
5
Label $E$ : order 5, final value $10$ . Update $F = \min(14,\ 10 + 3) = 13$ . Label $F$ : order 6, final value $13$ .
Stop once the destination $F$ is permanently labelled.
6
Trace back from $F$ : $13 - 3 = 10$ ( $E$ ), $10 - 2 = 8$ ( $D$ ), $8 - 5 = 3$ ( $B$ ), $3 - 1 = 2$ ( $C$ ), $2 - 2 = 0$ ( $A$ ).
Edge $XY$ lies on the route when (final value at $Y$ ) $-$ (final value at $X$ ) $=$ weight of $XY$ .

Answer: Shortest route $ACBDEF$ , length $13$