Problem Statement
A telecommunications network connects six hubs $A, B, C, D, E, F$ with fiber-optic line lengths (in km) given by weights:\n\n$AB = 7, AC = 9, AD = 14, BC = 10, BD = 15, CD = 11, CE = 2, DF = 6, EF = 9$.
**(a)** [5 marks] Use Dijkstra's algorithm to find the shortest network route and total distance from hub $A$ to hub $F$.
**(b)** [4 marks] Use Kruskal's algorithm to determine the minimum spanning tree (MST) connecting all 6 hubs, stating the order of edges chosen and total tree weight.
Verified Solution & Marking Scheme
Part (a) [M1]
Initializing labels: $A=0$. Order of finalized vertices: $A(0) \to B(7) \to C(9) \to E(11) \to F(20)$ or $D(20)$
Part (a) [A1]
Path $A \to C = 9$; $A \to C \to E = 9 + 2 = 11$; $A \to C \to E \to F = 11 + 9 = 20$
Part (a) [A1]
Alternative $A \to D = 14 \to F = 14 + 6 = 20$
Part (a) [A1]
Shortest paths: $A-C-E-F$ or $A-D-F$
Part (a) [A1]
Minimum distance $= 20\text{ km}$
Part (b) [M1]
Sort edges by ascending weight: $CE(2), DF(6), AB(7), EF(9), AC(9), BC(10), CD(11), AD(14), BD(15)$
Part (b) [A1]
Edge selection without creating cycles: Select $CE (2)$, select $DF (6)$, select $AB (7)$, select $EF (9)$, select $AC (9)$
Part (b) [A1]
Edges chosen: $\{CE, DF, AB, EF, AC\}$ (5 edges for 6 vertices)
Part (b) [A1]
Total MST weight $= 2 + 6 + 7 + 9 + 9 = 33\text{ km}$