Shortest Path Algorithms (Dijkstra's)

Every satnav, every internet router and every logistics planner is, underneath, solving the same problem: given a network and a starting point, what is the cheapest way to reach each destination? Dijkstra's algorithm answers this for any network with non-negative edge weights, and it does so with a beautifully simple greedy idea — repeatedly "lock in" the nearest still-unfinished vertex. It is among the most important algorithms in all of discrete mathematics and computer science, and in AQA 7367 it is examined as a precise label-updating procedure that you must execute and communicate cleanly.

---

1. Where this sits in AQA 7367

Shortest-path is a central algorithm of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Running Dijkstra correctly and reading off a route is AO1; justifying the greedy step and arguing why non-negativity is essential is AO2; applying it inside a larger model (e.g. as a subroutine of route inspection) is AO3. AQA expects a fully worked labelling diagram with permanent labels, working values and an order of labelling.

---

2. The problem

Given a network $G = (V, E)$G=(V,E) with non-negative weights $w(e) \ge 0$w(e)≥0 and a source vertex $S$S, find, for every vertex $v$v, the minimum total weight $d(v)$d(v) of a path from $S$S to $v$v — and the route achieving it. We write $d(v)$d(v) for this shortest distance.

---

3. Core theory: Dijkstra's algorithm

Each vertex carries a label with three pieces of information (the standard AQA box):

• the order of labelling (1st, 2nd, … to be made permanent),
• the permanent label $d(v)$d(v) — the confirmed shortest distance from $S$S,
• the working (temporary) values — successively improved estimates.

Procedure

1. Give $S$S the permanent label $d(S) = 0$d(S)=0 and order $1$1; all other working values start at $\infty$∞.
2. From the vertex $V$V just made permanent, relax each edge to an unfinished neighbour $U$U: replace its working value by $\min\bigl(\text{current working value of } U,\ d(V) + w(VU)\bigr).$min(current working value of U, d(V)+w(VU)).
3. Among all unfinished vertices, the one with the smallest working value becomes permanent next (record its order and $d$d).
4. Repeat from step 2 until every vertex is permanent (or the target is reached).

The greedy step in (3) is justified by non-negativity: the chosen vertex cannot later be reached more cheaply via some other unfinished vertex, because any such detour would start from a working value at least as large and then add a non-negative weight.

---

4. Worked Example 4.1 (with M1/A1 mark scheme)

Network on A, B, C, D, E with the edges below. Find the shortest path from A to every vertex.

Edge	AB	AC	BC	BD	CD	CE	DE
Weight	4	2	1	5	8	10	2

Trace of the labelling (order — permanent — final source vertex):

Order	Vertex	Permanent $d$d	Reached from
1	A	0	—
2	C	2	A
3	B	3	C
4	D	8	B
5	E	10	D

Step commentary (the working-value updates examiners want to see):

• Make A permanent $(d = 0)$(d=0). Relax: $B \leftarrow 4,\ C \leftarrow 2$B←4, C←2. Smallest is C(2) → permanent. (M1 for correct first relaxation; A1 for $d(C)=2$d(C)=2.)
• From C: $B \leftarrow \min(4,\ 2+1) = 3,\ D \leftarrow \min(\infty,\ 2+8) = 10,\ E \leftarrow \min(\infty,\ 2+10) = 12$B←min(4, 2+1)=3, D←min(∞, 2+8)=10, E←min(∞, 2+10)=12. Smallest unfinished is B(3) → permanent. (M1 the improvement $4 \to 3$4→3; A1 $d(B)=3$d(B)=3.)
• From B: $D \leftarrow \min(10,\ 3+5) = 8$D←min(10, 3+5)=8. Smallest unfinished is D(8) → permanent. (A1 $d(D)=8$d(D)=8.)
• From D: $E \leftarrow \min(12,\ 8+2) = 10$E←min(12, 8+2)=10. E(10) → permanent. (A1 $d(E)=10$d(E)=10.)

Shortest paths from A (trace back through the "reached from" column):

Vertex	$d(v)$d(v)	Route
A	0	$A$A
C	2	$A \to C$A→C
B	3	$A \to C \to B$A→C→B
D	8	$A \to C \to B \to D$A→C→B→D
E	10	$A \to C \to B \to D \to E$A→C→B→D→E

(A1 for each correct route; note the route to D is not the direct edge AD-type guess — the working values force the via-C-B route.)

graph LR
  A((A 0)) ---|2| C((C 2))
  C ---|1| B((B 3))
  B ---|5| D((D 8))
  D ---|2| E((E 10))

Exam tip. A vertex's permanent label can be improved while it is still temporary (here B fell from $4$4 to $3$3) but is frozen once made permanent. Always show the superseded working values — examiners reward the full update trail.

---

5. Worked Example 4.2 — a different source

Network with edges SA(2), SB(5), AB(2), AC(4), BC(1), BD(4), CD(3), CE(6), DE(2). Shortest paths from S.

Order	Vertex	Permanent $d$d	Reached from
1	S	0	—
2	A	2	S
3	B	4	A
4	C	5	B
5	D	8	B
6	E	10	D

Key updates: from S, $A \leftarrow 2,\ B \leftarrow 5$A←2, B←5; A made permanent; from A, $B \leftarrow \min(5, 2+2) = 4,\ C \leftarrow 2+4 = 6$B←min(5,2+2)=4, C←2+4=6; B made permanent; from B, $C \leftarrow \min(6, 4+1) = 5,\ D \leftarrow 4+4 = 8$C←min(6,4+1)=5, D←4+4=8; C made permanent; from C, $D \leftarrow \min(8, 5+3) = 8$D←min(8,5+3)=8 (tie — keep $8$8), $E \leftarrow 5+6 = 11$E←5+6=11; D made permanent; from D, $E \leftarrow \min(11, 8+2) = 10$E←min(11,8+2)=10; E made permanent. So, e.g., $d(E) = 10$d(E)=10 via $S \to A \to B \to D \to E$S→A→B→D→E. The relabel $B:\ 5 \to 4$B: 5→4 is exactly the kind of improvement examiners look for. Notice the tie at D: both $S\!-\!A\!-\!B\!-\!D$S−A−B−D and $S\!-\!A\!-\!B\!-\!C\!-\!D$S−A−B−C−D cost $8$8. When working values tie, either predecessor is acceptable — but you should pick one and stay consistent so your traced route is unambiguous.

5b. Worked Example 4.3 — a seven-vertex network

Network with edges AB(3), AC(6), BC(2), BD(4), CD(1), CE(5), DE(3), DF(6), EF(2), EG(4), FG(3). Find the shortest distance from A to every vertex, and the route to G.

Order	Vertex	Permanent $d$d	Reached from
1	A	0	—
2	B	3	A
3	C	5	B
4	D	6	C
5	E	9	D
6	F	11	E
7	G	13	E

Step commentary:

• A permanent $(0)$(0); relax $B \leftarrow 3,\ C \leftarrow 6$B←3, C←6. Smallest is B(3).
• From B: $C \leftarrow \min(6,\ 3+2) = 5,\ D \leftarrow 3+4 = 7$C←min(6, 3+2)=5, D←3+4=7. Smallest unfinished is C(5).
• From C: $D \leftarrow \min(7,\ 5+1) = 6,\ E \leftarrow 5+5 = 10$D←min(7, 5+1)=6, E←5+5=10. Smallest is D(6).
• From D: $E \leftarrow \min(10,\ 6+3) = 9,\ F \leftarrow 6+6 = 12$E←min(10, 6+3)=9, F←6+6=12. Smallest is E(9).
• From E: $F \leftarrow \min(12,\ 9+2) = 11,\ G \leftarrow 9+4 = 13$F←min(12, 9+2)=11, G←9+4=13. Smallest is F(11).
• From F: $G \leftarrow \min(13,\ 11+3) = 13$G←min(13, 11+3)=13 (tie — keep $13$13). G(13) permanent.

The shortest route to G traces back $G \leftarrow E \leftarrow D \leftarrow C \leftarrow B \leftarrow A$G←E←D←C←B←A, i.e. $A \to B \to C \to D \to E \to G$A→B→C→D→E→G of length $13$13. Three different working values were improved en route (C from $6$6 to $5$5, D from $7$7 to $6$6, E from $10$10 to $9$9) — visible evidence that the algorithm keeps refining estimates until each is locked in. This is the level of annotated working AQA rewards in a five-mark Dijkstra question.

---

6. Why it works, and its complexity

Correctness. When a vertex $V$V is made permanent with value $t$t, claim $d(V) = t$d(V)=t. Any other $S\to V$S→V path leaves the finished set at some edge into an unfinished vertex $U$U; that $U$U had working value $\ge t$≥t (else $U$U, not $V$V, would have been chosen), and the rest of the path adds non-negative weight, so the alternative path costs $\ge t$≥t. Hence $t$t is optimal. $\blacksquare$■ This argument fails if weights can be negative — the rest of a path could reduce the total.

Complexity. A basic array implementation is

$O(n^2),$O(n2),

where $n = |V|$n=∣V∣; with a binary-heap priority queue it improves to $O\bigl((n + m)\log n\bigr)$O((n+m)logn) for $m = |E|$m=∣E∣. Both are polynomial — Dijkstra is efficient, in sharp contrast to the exponential travelling-salesman problem. The $O(n^2)$O(n2) figure comes from the structure of the work: there are $n$n "make-permanent" steps, and each scans the remaining at most $n$n working values to find the minimum, giving $n \times n = n^2$n×n=n2; the relaxations cost $O(m)$O(m) in total, which is dominated by $n^2$n2 for the array version. Replacing the linear scan by a heap turns each minimum-extraction into $O(\log n)$O(logn) and each relaxation's update into $O(\log n)$O(logn), which is why sparse networks (where $m$m is comparable to $n$n) run so much faster with a priority queue.

Relationship to breadth-first search

When every edge weight is $1$1, Dijkstra's algorithm degenerates into breadth-first search (BFS): vertices become permanent strictly in order of their hop-distance from the source, and the working values are simply "edges so far". Seeing Dijkstra as a weighted generalisation of BFS demystifies the greedy step — with unit weights the nearest unfinished vertex is obviously the next layer out, and adding non-negative weights merely deforms "layers" into "distance shells" while preserving the order-by-distance guarantee. This is also why a negative weight is fatal: it would let a "shell" reach back inside an already-settled region, destroying the layered order.

A note on single-source vs single-pair

The procedure naturally computes shortest distances to all vertices. If only one target $T$T is wanted, you may stop the moment $T$T is made permanent — every later vertex is at least as far, so it cannot lie on a shorter $S\!-\!T$S−T route. In the exam, read the command: "find the shortest path from A to E" lets you halt at E, but "complete the table of shortest distances from A" requires every vertex to be labelled. Either way, the labels you have already committed are exactly the data you trace back for any requested route — never recompute.

---

7. Specimen-style exam question

(Specimen-style — not from any past paper.)

The network shows times (minutes) to travel between six junctions A–F: AB(2), AC(5), BC(2), BD(4), CE(3), DE(1), DF(6), EF(2). (a) Use Dijkstra's algorithm to find the shortest time from A to F. Show the order of labelling and the permanent label at each vertex. [5] (b) State the corresponding route. [1]