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

You will apply Dijkstra's algorithm with Pearson's working and permanent labels, recover shortest paths, and use a specified starting node to find a shortest route that must pass through it.

What the labels mean

A direct road from $A$ to $B$ has length $8$ , but going through $C$ takes only $3+2=5$ . How can an algorithm recognise that improvement without trying every possible route? It keeps a best distance so far, and only makes that distance permanent when it is safe.

You already know

Arc weights give distances, times or costs. A path follows the graph's connections; an arrow permits travel only in its indicated direction. A shortest path minimises the sum of the weights used.

Dijkstra's algorithm works on directed or undirected networks with non-negative weights. In a directed network, only outgoing arcs can be used from the current node. A missing connection is not an arc of weight zero.

[DIAGRAM: asset_name: Pearson's Dijkstra label compartments; asset_slug: 9fm0-d1-167-label-box; caption: Node name, order of becoming permanent and final distance occupy separate top cells; working values stay below.; description: A three-cell top row B, 3, 5 above one working-values row containing 8 then 5, with clearly separated annotations identifying each field.]

Working and permanent labels

A working value is the shortest distance found so far from the specified start. Replace it only when a smaller candidate is found, retaining the old values in their chronological order.

A permanent label is the confirmed shortest distance. Record separately the order in which the node becomes permanent. We number that order $1,2,3,\ldots$ , starting at the specified source.

In the pictured box, $B$ became permanent third with distance $5$ ; its working value improved from $8$ to $5$ . The order $3$ is not a distance. If two nodes become permanent with the same distance, their order numbers must still be different and increasing.

Key idea

The order label says when a node became permanent. The distance label says how far it is from the start. Keep both, together with the working-value history.

The direct $A$ -to- $B$ road is not enough to settle $B$ 's shortest distance.

Applying Dijkstra's algorithm

Make the specified start permanent with distance zero. Each time a node becomes permanent, use its distance to update its non-permanent neighbours. Then choose the smallest current working value anywhere in the network.

Dijkstra's algorithm

Give the specified start permanent distance $0$ and first order label.
From the newest permanent node $u$ , calculate each permitted candidate $d(u)+w(u,v)$ for a non-permanent neighbour $v$ . Write it only if it improves $v$ 's current working value.
Make a node with the least working value permanent, and give it the next order label.
Repeat until the destination is permanent, or all reachable nodes are permanent if all distances are needed.

Here $d(u)$ is the permanent distance and $w(u,v)$ the arc weight. For an equal candidate, retain the current value; it may reveal another shortest route. If several nodes tie for least working value, either can be made permanent next unless instructed otherwise. We use alphabetical node order for these traces.

Not in the formula booklet: learn it.

Why is the smallest working value safe? Any competing route that has not yet been explored must reach an unlabelled node first. Its distance cannot undercut the current smallest working value when all remaining arc weights are non-negative. Negative weights would break that argument.

[DIAGRAM: asset_name: A network for a complete Dijkstra trace; asset_slug: 9fm0-d1-167-trace-network; caption: Use the given weights, and start at A; the top cells and lower working boxes follow Pearson's layout.; description: Six-node undirected network with AB8, AC3, BC2, BD4, CD9, CE5, DE1, DF7, EF2 and BE8; each node is shown as a three-cell top label box above a working-values compartment.]

Worked example 1: improvements and a tied predecessor

Question. Apply Dijkstra's algorithm from $A$ to the network

AB=8,\ AC=3,\ BC=2,\ BD=4,\ CD=9,\ CE=5,\ DE=1,\ DF=7,\ EF=2,\ BE=8

Find the shortest distances to every node.

Plan. Make the least working value permanent at each step, retaining only improving updates in the working boxes.

Order	New permanent node and distance	Updates and comparisons
$1$	$A:0$	$B=8,\ C=3$
$2$	$C:3$	$B:8\to5,\ D=12,\ E=8$
$3$	$B:5$	$D:12\to9$ ; candidate $E=13$ does not improve $8$
$4$	$E:8$	$F=10$ ; candidate $D=9$ equals its current value
$5$	$D:9$	Candidate $F=16$ does not improve $10$
$6$	$F:10$	All nodes permanent

The completed label information is:

Node	Order	Permanent distance	Working values, in order
$A$	$1$	$0$	$0$
$B$	$3$	$5$	$8,5$
$C$	$2$	$3$	$3$
$D$	$5$	$9$	$12,9$
$E$	$4$	$8$	$8$
$F$	$6$	$10$	$10$

Why not write $13$ after $8$ at $E$ ? It is a worse candidate, so it is not a new working value. Likewise, an equal candidate need not be copied again.

Answer. The shortest distances from $A$ to $B,C,D,E,F$ are $5,3,9,8,10$ , respectively.

Check. Permanent distances occur in non-decreasing order $0,3,5,8,9,10$ . Every final distance is achieved by an actual route.

Worked example 2 changes only $AB$ , from $8$ to $4$ . This creates a tie in the permanent distances and a new working-value history at $F$ .

Worked example 2: equal distances, different order labels

Question. Apply Dijkstra from $A$ when

AB=4,\ AC=3,\ BC=2,\ BD=4,\ CD=9,\ CE=5,\ DE=1,\ DF=7,\ EF=2,\ BE=8

Break ties between nodes alphabetically.

Plan. Recalculate the trace from the changed initial value; do not merely alter $B$ 's final box.

Order	New permanent node and distance	Updates and comparisons
$1$	$A:0$	$B=4,\ C=3$
$2$	$C:3$	$D=12,\ E=8$ ; candidate $B=5$ is worse than $4$
$3$	$B:4$	$D:12\to8$ ; candidate $E=12$ is worse than $8$
$4$	$D:8$	$F=15$ ; candidate $E=9$ is worse than $8$
$5$	$E:8$	$F:15\to10$
$6$	$F:10$	Complete

Node	Order	Permanent distance	Working values, in order
$A$	$1$	$0$	$0$
$B$	$3$	$4$	$4$
$C$	$2$	$3$	$3$
$D$	$4$	$8$	$12,8$
$E$	$5$	$8$	$8$
$F$	$6$	$10$	$15,10$

Why do $D,E$ have orders $4,5$ rather than the same order? Only their distances tie. The algorithm makes them permanent in two successive decisions.

Answer. The permanent order is $A,C,B,D,E,F$ ; the distances are $0,3,4,8,8,10$ in that order.

Check. $A,B,D$ has length $4+4=8$ , and $A,C,E$ has length $3+5=8$ , confirming the tied distances.

A node is finished only when it is permanent, not when a first working value reaches it. If the least remaining working value is $\infty$ , no remaining node can be reached from the start; stop rather than assigning a finite route.

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 Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D1 2.2 - Dijkstra's algorithm

What the labels mean

Applying Dijkstra's algorithm

Continue this lesson.

Learn faster with Nova