Solutions — Shortest Path Problems — Grade 12 General Maths

Fluency Edges AB=3, AC=7, BC=2, BD=5, CD=1. Shortest A to D by inspection.

All paths from A to D:
A→B→D: 3+5 = 8
A→C→D: 7+1 = 8
A→B→C→D: 3+2+1 = 6
A→C→B→D: 7+2+5 = 14

Shortest path: A → B → C → D, total weight = 6

Fluency Dijkstra’s algorithm: AB=6, AC=3, BC=2, BD=7, CD=4. Shortest A to D.

Step	Visit	B	C	D
Start	A	6	3	∞
1	C	5	3	7
2	B	5	3	7
3	D	5	3	7

After visiting C: B updated to 3+2=5 (was 6); D updated to 3+4=7.
Shortest path A to D = 7, via A → C → D

Fluency Edges ST=5, SU=8, TU=3, TV=6, UV=4, VW=2. Shortest S to W.

Dijkstra from S: S=0, T=5, U=8 → visit T(5): U→min(8,8)=8, V→11 → visit U(8): V→min(11,12)=11 → visit V(11): W→13 → visit W(13).

Shortest path: S → T → V → W = 5+6+2 = 13

Fluency Permanent labels in order: A=0, C=4, B=6, D=9, E=11.

These permanent labels tell us the shortest distance from A to each vertex:
A to A = 0 (trivially)
A to C = 4
A to B = 6
A to D = 9
A to E = 11

Understanding Dijkstra’s from P to T: PQ=10, PR=3, QR=4, QS=2, RS=8, RT=15, ST=5.

Step	Visit	Q	R	S	T
Start	P	10	3	∞	∞
1	R	7	3	11	18
2	Q	7	3	9	18
3	S	7	3	9	14
4	T	7	3	9	14

Trace back: T(14) ← S(9)+5; S(9) ← Q(7)+2; Q(7) ← R(3)+4; R(3) ← P(0)+3.
Shortest path: P → R → Q → S → T = 3+4+2+5 = 14

Understanding Road network: AB=12, AC=5, BD=8, BC=4, CD=7, CE=11, DE=3, EF=6, DF=9. Shortest A to F.

Dijkstra from A: A=0; B→12, C→5.
Visit C(5): B→min(12,9)=9, D→12, E→16.
Visit B(9): D→min(12,17)=12 (no change).
Visit D(12): E→min(16,15)=15, F→21.
Visit E(15): F→min(21,21)=21.
Visit F(21).

Trace: F(21) ← D(12)+9; D(12) ← C(5)+7; C(5) ← A(0)+5.
Shortest path: A → C → D → F = 5+7+9 = 21 km
(Also: A→C→D→E→F = 5+7+3+6 = 21 km — same length, different route.)

Understanding Dijkstra’s from vertex 1 to 5: 1–2=7, 1–3=9, 1–6=14, 2–3=10, 2–4=15, 3–4=11, 3–6=2, 4–5=6, 5–6=9.

Start: 1=0; 2→7, 3→9, 6→14.
Visit 2(7): 3→min(9,17)=9, 4→22.
Visit 3(9): 4→min(22,20)=20, 6→min(14,11)=11.
Visit 6(11): 5→20.
Visit 4(20): 5→min(20,26)=20 (no change).
Visit 5(20).

Trace: 5(20) ← 6(11)+9; 6(11) ← 3(9)+2; 3(9) ← 1(0)+9.
Shortest path: 1 → 3 → 6 → 5 = 9+2+9 = 20

Understanding Network transmission times: AB=20, AC=10, BD=15, BC=25, CD=5, CE=30, DE=10. Fastest A to E.

Dijkstra from A: A=0; B→20, C→10.
Visit C(10): B→min(20,35)=20, D→15, E→40.
Visit D(15): E→min(40,25)=25.
Visit B(20): (no shorter paths from B to remaining vertices).
Visit E(25).

Trace: E(25) ← D(15)+10; D(15) ← C(10)+5; C(10) ← A(0)+10.
Fastest route: A → C → D → E = 10+5+10 = 25 ms

Problem Solving Courier D to Z: DA=4, DB=8, AC=3, BC=6, AE=5, CE=2, BE=7, EZ=10, CZ=15.

Dijkstra from D: D=0; A→4, B→8.
Visit A(4): C→7, E→9.
Visit C(7): E→min(9,9)=9, Z→22.
Visit B(8): C→min(7,14)=7 (no change), E→min(9,15)=9 (no change).
Visit E(9): Z→min(22,19)=19.
Visit Z(19).

Trace: Z(19) ← E(9)+10; E(9) ← A(4)+5; A(4) ← D(0)+4.
Shortest route: D → A → E → Z = 4+5+10 = 19
(Alternative: D→A→C→E→Z = 4+3+2+10 = 19, same length.)

Problem Solving Graph AB=2, AC=5, AD=1, BC=3, BD=4, CD=2, CE=7, DE=5, DF=8, EF=3.

Dijkstra from A (all shortest distances):
Start: A=0; B→2, C→5, D→1.
Visit D(1): B→min(2,5)=2, C→min(5,3)=3, E→6, F→9.
Visit B(2): C→min(3,5)=3 (no change).
Visit C(3): E→min(6,10)=6 (no change).
Visit E(6): F→min(9,9)=9 (no change).
Visit F(9).

Permanent labels: A=0, D=1, B=2, C=3, E=6, F=9

(a) Shortest A to F = 9
Path: F(9) ← D(1)+8 or E(6)+3 (tied).
Via D: A → D → F = 1+8=9 ✓
Via E: A → D → E → F = 1+5+3=9 ✓

(b) Shortest A to E = 6
Path: E(6) ← D(1)+5; A → D → E = 1+5=6 ✓

(c) Hardest to reach from A: F (distance 9)