AN6, AN7 - Dijkstra's algorithm and complexity | OCR A-Level Further Mathematics B (MEI)

Find shortest paths with Dijkstra's algorithm, keeping working labels, permanent labels and predecessor routes distinct. AN6 handles undirected and directed networks; AN7 compares the prescribed quadratic complexity of Dijkstra, Kruskal and Prim using the correct measure of input size.

Make shortest-distance labels permanent

The first route you find to a destination has length $9$ . Must that be its shortest distance? In the network below, a later route has length $7$ . Dijkstra's algorithm tells you when a provisional distance can finally be trusted.

You already know

A network's weights must represent the quantity being minimised. A minimum connector minimises an entire installed system; a shortest path minimises one journey. Record algorithm updates in order and use the stated input-size variable when discussing complexity.

Use non-negative arc weights. Give the starting vertex permanent label zero and all other vertices working label $\infty$ . From the most recently made permanent vertex, form candidate distances to its unlabelled neighbours: permanent distance plus arc weight. Replace a working label only if the candidate is smaller; record its predecessor.

Choose a vertex with the smallest working label, make that label permanent and record its order. Repeat. Stop for a specified destination when its label becomes permanent, not when it first receives a working value. Tied smallest labels may be processed in either order unless the question specifies a rule.

Dijkstra's update

If $u$ has permanent distance $d(u)$ and an arc of non-negative weight $w(u,v)$ leads to an unlabelled vertex $v$ , update

d_{\mathrm{work}}(v)\longleftarrow\min\bigl(d_{\mathrm{work}}(v),d(u)+w(u,v)\bigr)

The next permanent label is a smallest remaining working label.

Not in the formula booklet: learn it.

Non-negative weights make the choice safe: a route through a vertex with a larger provisional distance cannot later come back with a smaller distance to the vertex being fixed. Negative weights would break that argument.

[DIAGRAM: asset_name: Working labels improve before becoming permanent; asset_slug: dijkstra_working_labels; caption: The provisional label at E falls from 9 to 7 before E becomes permanent; description: An undirected network on A, B, C, D, E has weights AB 4, AC 1, BC 2, BD 1, CD 5, CE 8, DE 3. The shortest path A to C to B to D to E is highlighted. Small labels show final distances A 0, C 1, B 3, D 4, E 7, and a separate annotation identifies E's earlier working value 9.]
The provisional label at E falls from 9 to 7 before E becomes permanent

Worked example 1: retain the working updates

Question. Apply Dijkstra's algorithm from $A$ to $E$ in the displayed network, with weights $AB=4,AC=1,BC=2,BD=1,CD=5,CE=8,DE=3$ . Find a shortest path and its length.

Plan. Make the smallest working label permanent each time, updating all its unlabelled neighbours.

Newly permanent vertex	Permanent label	Working-label changes made from it
$A$ , first	$0$	$B: \infty\to4$ , $C:\infty\to1$
$C$ , second	$1$	$B:4\to3$ , $D:\infty\to6$ , $E:\infty\to9$
$B$ , third	$3$	$D:6\to4$
$D$ , fourth	$4$	$E:9\to7$
$E$ , fifth	$7$	Destination permanent; stop.

\begin{aligned} \text{predecessors backwards}&:\quad E\leftarrow D\leftarrow B\leftarrow C\leftarrow A &&\text{follow successful updates}\\ \text{path length}&=1+2+1+3=7 &&\text{check the reconstructed path} \end{aligned}

Why this step? The first working value at $E$ is $9$ , but it is not permanent while a shorter route through $B,D$ remains to be explored.

Answer. A shortest path is $ACBDE$ , length $7$ .

Check. Permanent labels are $0,1,3,4,7$ , in non-decreasing order, and the path's arc sum is $7$ .

Change only $AB$ 's weight from $4$ to $2$ . An earlier working value may now survive instead of being improved via $C$ .

Worked example 2: a different best predecessor

Question. Apply Dijkstra's algorithm after this change, again from $A$ to $E$ .

Plan. Use the same permanent-label rule, but recalculate the candidate distances involving $AB$ .

Newly permanent vertex	Label	Working-label changes or comparisons
$A$	$0$	$B:2$ , $C:1$
$C$	$1$	Candidate $B=3$ does not improve $2$ ; set $D=6,E=9$ .
$B$	$2$	$D:6\to3$
$D$	$3$	$E:9\to6$
$E$	$6$	Stop.

\begin{aligned} \text{predecessors}&:\quad E\leftarrow D\leftarrow B\leftarrow A &&\text{retain the best incoming update}\\ \text{length}&=2+1+3=6 &&\text{sum along }ABDE \end{aligned}

Why this step? An update is a minimum comparison, not an instruction to replace a smaller existing label with the latest candidate.

Answer. $ABDE$ , length $6$ .

Check. $ACBDE$ still has length $7$ , so the changed direct connection to $B$ really gives an improvement.

In a diagram trace, preserve working values visibly, distinguish permanent labels and number the order. Then state the actual path as well as its length.

Watch out

Wrong: replace the working label $B=2$ by the new candidate $1+2=3$ . A later candidate need not be better. Correct: retain $\min(2,3)=2$ , and its existing predecessor, then continue the smallest-working-label rule.

Retain every improvement, but reject larger candidates, in the next trace.

Respect directions and retain tied shortest paths

In a digraph, update along arrows leaving the permanent vertex. An arc pointing into it cannot be traversed backwards. If a candidate equals a current best distance, the distance stays the same, but there may be another shortest predecessor.

When all shortest paths are requested, retain equal predecessor alternatives and reconstruct each valid route. This reconstruction procedure assumes positive arc weights, as in the examples here; zero-weight arcs need additional care with equal predecessors, even though Dijkstra still gives correct distances. Equal working labels do not mean the corresponding vertices must lie on the same path.

[DIAGRAM: asset_name: Equal shortest paths in a digraph; asset_slug: dijkstra_directed_ties; caption: Two equal routes enter C from different predecessors, producing two shortest paths to T; description: A directed network has S to A 2, S to B 2, A to C 2, B to C 2, C to T 3, A to T 7, B to T 8. Arrows run left to right. Both S A C T and S B C T are highlighted, each of length 7. An annotation states that changing B to C from 2 to 1 leaves only S B C T shortest, of length 6.]
Two equal routes enter C from different predecessors, producing two shortest paths to T

Worked example 3: two shortest routes

Question. Apply Dijkstra from $S$ to $T$ in the displayed digraph, using alphabetical order for tied permanent-label choices. Find all shortest paths.

Plan. Follow outgoing arrows and keep both predecessors when they give the same best distance.

Newly permanent vertex	Label	Updates
$S$	$0$	$A=2,B=2$ .
$A$	$2$	$C=4,T=9$ .
$B$	$2$	Candidate $C=4$ : retain both $A,B$ ; candidate $T=10$ : no improvement.
$C$	$4$	$T:9\to7$ .
$T$	$7$	Stop.

\begin{aligned} S\!A\!C\!T&:\quad2+2+3=7 &&\text{predecessor }A\text{ at }C\\ S\!B\!C\!T&:\quad2+2+3=7 &&\text{predecessor }B\text{ at }C \end{aligned}

Why this step? The equal candidate at $C$ adds another shortest route, even though it does not change the distance label.

Answer. $SACT$ and $SBCT$ , both length $7$ .

Check. Direct alternatives through $AT$ or $BT$ have lengths $9$ and $10$ , so neither is shortest.

Change only $BC$ 's directed weight from $2$ to $1$ . The tie at $C$ is broken.

Continue this lesson.

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

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AN6, AN7 - Dijkstra's algorithm and complexity

Make shortest-distance labels permanent

Respect directions and retain tied shortest paths

Continue this lesson.

Learn faster with Nova