D1 2.2 - Dijkstra's algorithm | Edexcel A-Level International Mathematics

Find a shortest route through a weighted network by keeping tentative distances and fixing them in a safe order. You will show Dijkstra's working values, recover the route from the final labels, and interpret changes when a road closes.

Temporary and permanent labels

Can the shortest route begin with an edge that is not the shortest-looking line on the page? The numbers, rather than the drawn lengths, decide. Even the smallest edge from your current position need not lead towards the best overall route.

Dijkstra's algorithm works here on a connected, undirected network with nonnegative edge weights. A label is a distance from the chosen start, not the length of the most recent edge.

Temporary and permanent labels

A temporary label, also called a working value, is the shortest distance to that vertex found so far. It may decrease. A permanent label, or final value, is the established shortest distance from the start. Record its order of labelling separately: order $3$ does not mean distance $3$ .

Set the start's permanent distance to $0$ , with order $1$ . Initially other distances are unknown, represented by $\infty$ . From the newly permanent vertex $U$ , calculate

\text{candidate at }V=\text{final distance at }U+\text{weight of }UV.

Update an unlabelled neighbour only when this improves its temporary value. Then make the smallest temporary value anywhere in the network permanent. If smallest values tie, either tied vertex may be selected next; use distinct order numbers.

[DIAGRAM: asset_name: A shortest-path network; asset_slug: dijkstra-network; caption: A working value measures the whole route from A, not just the last edge.; description: Undirected edges AB 7 AC 3 BC 2 BD 4 CD 8 CE 5 DE 1 DF 6 EF 4 BF 15 on vertices A B C D E F. A separate key shows vertex, order, final value and ordered working values.]

Worked example 1: the first update

On this network, start at $A$ .

Plan. Fix $A$ at zero and update its two neighbours.

The candidates are $0+7=7$ at $B$ and $0+3=3$ at $C$ . All other vertices remain unknown.

Answer. Temporary values $B:7,C:3$ ; select $C$ next, with order $2$ and final value $3$ .

Check. These are the two one-edge routes from $A$ , and $3<7$ .

Change only the vertex being processed, from $A$ to the newly fixed $C$ . This reveals an improvement to an earlier estimate.

Worked example 2: revising a working value

Process $C$ , whose final distance is $3$ .

Plan. Add each edge from $C$ to $3$ , ignoring already permanent $A$ .

B:3+2=5<7,\qquad D:3+8=11,\qquad E:3+5=8.

Keep $B$ 's working values in the order $7,5$ ; do not erase the earlier $7$ . Now compare all temporary values $5,11,8$ .

Answer. Select $B$ next, with order $3$ , final value $5$ .

Check. The route $A,C,B$ has length $3+2=5$ , less than direct $AB=7$ .

Why may the smallest temporary label be fixed? Any route through an unfixed vertex must first reach an unfixed vertex at least this far away. Adding nonnegative edge lengths cannot produce a smaller arrival at the chosen vertex. Negative weights would break that argument.

Watch out

Choose the smallest total temporary distance, not the smallest outgoing edge. Keep improving working values in their actual order; a correct final value alone does not show the algorithm.

Apply one update before choosing the next vertex.

Finding a shortest distance

Continue the updates until the destination is permanent; a temporary destination label can still improve.

Use a table to make the trace readable. A dash below means no new improving value, rather than a zero distance. When a candidate is larger than or equal to a current working value, retain that current value; it need not be entered as a new working value.

Worked example 3: a complete trace

Find the shortest distance from $A$ to $F$ in the pictured network, whose edges are $AB=7,AC=3,BC=2,BD=4,CD=8,CE=5,DE=1,DF=6,EF=4,BF=15$ .

Plan. Process each newly permanent vertex and record every improvement before selecting the next minimum.

Order	Vertex fixed	Final distance	New improving working values
1	$A$	$0$	$B:7; C:3$
2	$C$	$3$	$B:5; D:11; E:8$
3	$B$	$5$	$D:9; F:20$
4	$E$	$8$	$F:12$
5	$D$	$9$	None: $9+6=15>12$ at $F$
6	$F$	$12$	Stop

At order $4$ , the candidate at $D$ is $8+1=9$ , equal to its current $9$ , so that label stays unchanged.

Answer. The shortest distance is $12$ . Ordered working values are $B:7,5; C:3; D:11,9; E:8; F:20,12$ .

Check. The final distances $A:0,B:5,C:3,D:9,E:8,F:12$ satisfy $d(V)\le d(U)+UV$ in both directions on every edge. For example $d(F)=12\le9+6$ and $d(D)=9\le8+1$ . A route $A,C,E,F$ actually attains $12$ , confirming the distance.

Change just $CE$ from $5$ to $9$ . This delays $E$ , so both the order and $F$ 's working values change.

Worked example 4: a revised edge

Repeat Dijkstra's algorithm with $CE=9$ , all other edges unchanged.

Plan. Recalculate the trace; do not keep the old permanent order automatically.

Order	Vertex fixed	Final distance	New improving working values
1	$A$	$0$	$B:7; C:3$
2	$C$	$3$	$B:5; D:11; E:12$
3	$B$	$5$	$D:9; F:20$
4	$D$	$9$	$E:10; F:15$
5	$E$	$10$	$F:14$
6	$F$	$14$	Stop

Answer. The shortest distance is $14$ , with $F$ 's working values $20,15,14$ .

Check. The route $A,C,B,D,E,F$ has length $3+2+4+1+4=14$ . All revised final labels satisfy the edge inequalities above, so no route can beat them.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Mathematics 1

Pure Mathematics 2

Pure Mathematics 3

Pure Mathematics 4

Mechanics 1

Mechanics 2

Statistics 1

Statistics 2

Decision Mathematics 1

D1 2.2 - Dijkstra's algorithm

Temporary and permanent labels

Finding a shortest distance

Continue this lesson.

Learn faster with Nova