7.04a - Dijkstra's algorithm | OCR A-Level Further Mathematics A

Find a shortest route without trying every possible journey. You will use temporary and permanent labels, recover a route from its distances, adapt the calculation to restrictions, and explain the algorithm's conditions and quadratic order.

Temporary and permanent labels

Can the first route you find to a destination be too long, even when every choice so far looked sensible? In the network below, the direct arc from $C$ to $E$ has weight $10$ , but travelling through $B$ and $D$ costs only $1+5+2=8$ . A distance must be allowed to improve before you trust it.

You already know

A network has weights on its arcs. The weight of a route is the sum of its arc weights. A directed arc can be used only in its arrow's direction; a dash in a weight table means that no direct arc exists.

Dijkstra's algorithm grows a region whose shortest distances from the start are known. A temporary label is the weight of the best route found so far; a permanent label is a shortest distance that has been settled. A label of $\infty$ means that no route has yet been found, not that a direct arc has infinite length.

[DIAGRAM: asset_name: Improving a route before settling it; asset_slug: h245_7_04_dijkstra_network; caption: Dijkstra's algorithm improves the temporary labels at D, E and F before making them permanent; description: Undirected network on A B C D E F with arcs AB 4 AC 2 BC 1 BD 5 CD 8 CE 10 DE 2 DF 6 EF 3. The shortest A to F route A C B D E F is highlighted. A separate inset shows the order and final distance at each vertex.]
Dijkstra's algorithm improves the temporary labels at D, E and F before making them permanent

Dijkstra's algorithm

For a finite network with non-negative arc weights:

Give the start permanent label $0$ and order label $1$ .
From the vertex just made permanent, with label $P$ , calculate $P+w$ along each permitted arc to a non-permanent neighbour. Replace its temporary label only if this improves it.
Make the smallest temporary label permanent. Break a tie either way, unless a rule is specified.
Repeat until the target is permanent, or all required distances are permanent. Trace back to recover the route.

In the formula booklet.

The choice in step 3 is global: compare all remaining temporary labels, rather than following the smallest arc from the last vertex. When showing labels on a diagram, put the permanence order at the upper left of the box, the permanent distance at the upper right, and the temporary labels below, as in the booklet. A table is also a clear way to preserve the updates.

Worked example 1: settling a shortest route

Question. Use Dijkstra's algorithm to find the shortest route from $A$ to $F$ in the diagram.

Plan. Start at $A$ , update neighbours, and repeatedly settle the smallest temporary distance.

The table records the best labels after updating from the vertex in the first column. A star marks a permanent label; the next vertex is chosen from the unstarred entries.

Updated from	$A$	$B$	$C$	$D$	$E$	$F$
$A$	$0^*$	$4$	$2$	$\infty$	$\infty$	$\infty$
$C$	$0^*$	$3$	$2^*$	$10$	$12$	$\infty$
$B$	$0^*$	$3^*$	$2^*$	$8$	$12$	$\infty$
$D$	$0^*$	$3^*$	$2^*$	$8^*$	$10$	$14$
$E$	$0^*$	$3^*$	$2^*$	$8^*$	$10^*$	$13$

For example,

\begin{aligned} d(B)&=\min(4,2+1)=3 &&\text{improve through }C\\ d(D)&=\min(10,3+5)=8 &&\text{improve through }B\\ d(E)&=\min(12,8+2)=10 &&\text{improve through }D\\ d(F)&=\min(14,10+3)=13 &&\text{improve through }E \end{aligned}

Now make $F$ permanent. The permanence order is $A,C,B,D,E,F$ .

Why this step? A temporary $F=14$ is not a stopping condition: the still-unsettled vertex $E$ can improve it.

Answer. Trace the updates backwards: $F,E,D,B,C,A$ . The shortest route is $A-C-B-D-E-F$ , of weight $13$ .

Check. Its actual arcs sum to $2+1+5+2+3=13$ .

The second example changes just the weight of $CD$ . A local change can alter several later distances, so rerun the updates rather than adjusting only the final total.

Worked example 2: one changed arc

Question. The same network now has $CD=4$ , with every other weight unchanged. Use Dijkstra's algorithm to find the shortest route from $A$ to $F$ .

Plan. Repeat the labels, preserving the improvement through the changed arc.

\begin{aligned} A=0&:\quad B=4,\ C=2 &&\text{start at }A\\ C=2&:\quad B=3,\ D=6,\ E=12 &&\text{update from }C\\ B=3&:\quad D=\min(6,3+5)=6 &&\text{retain the better label}\\ D=6&:\quad E=8,\ F=12 &&\text{update from }D\\ E=8&:\quad F=11 &&\text{improve through }E\\ F&=11 &&\text{make target permanent} \end{aligned}

Why this step? The route through $B$ is now worse for $D$ , so its existing temporary label must survive.

Answer. $A-C-D-E-F$ , of weight $11$ .

Check. $2+4+2+3=11$ . The old shortest route still has weight $13$ , so the new route is a genuine improvement.

Permanent and temporary labels do different jobs. Keep the update that produced each best label, or you may know the distance but lose the route.

Watch out

Wrong: stop when the target first receives a label. Right: stop when the target becomes permanent. In example 1, its first label is $14$ , but its shortest distance is $13$ .

The following table defines a different undirected network completely; only the listed arcs exist.

Arrows and restrictions

A shortest route is shortest among the routes the model permits, so remove a closed road or respect a one-way street before running the algorithm.

For a directed network, update only along arrows leaving the newly permanent vertex. A connection pointing into it does not let you travel backwards. An unreachable vertex keeps label $\infty$ ; if no finite temporary label remains, there is no permitted route to it. With equal smallest temporary labels, either can become permanent first. Equal distances may also correspond to different shortest routes, so do not claim uniqueness without checking.

Worked example 3: a directed network

Question. The only directed arcs are $S\to A$ of weight $4$ , $S\to B$ of weight $7$ , $A\to B$ of weight $1$ , $A\to T$ of weight $9$ and $B\to T$ of weight $3$ . Find the shortest route from $S$ to $T$ using Dijkstra's algorithm.

Plan. Update only along arrows pointing away from each settled vertex.

\begin{aligned} S=0&:\quad A=4,\ B=7 &&\text{outgoing arcs from }S\\ A=4&:\quad B=\min(7,4+1)=5,\ T=13 &&\text{update from }A\\ B=5&:\quad T=\min(13,5+3)=8 &&\text{update from }B\\ T&=8 &&\text{settle the target} \end{aligned}

Why this step? $A\to B$ lets the route reach $B$ more cheaply; it does not permit a journey from $B$ to $A$ .

Answer. $S-A-B-T$ , of weight $8$ .

Check. $4+1+3=8$ ; the alternatives $S-B-T$ and $S-A-T$ cost $10$ and $13$ .

Now change only the availability of $A\to B$ . The physical layout is unchanged, but the set of allowed journeys is smaller.

Continue this lesson.

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

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.04a - Dijkstra's algorithm

Temporary and permanent labels

Arrows and restrictions

Continue this lesson.

Learn faster with Nova