EXM.1.AHL.TZ0.23
Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F.
The possible roads and the costs of building them are shown in the graph below. Each vertex represents a town, each edge represents a road and the weight of each edge is the cost of building that road. He needs to design the lowest cost road system that will connect the six towns.
Name an algorithm that will allow Sameer to find the lowest cost road system.
Find the lowest cost road system and state the cost of building it. Show clearly the steps of the algorithm.
Markscheme / solution
EITHER
Prim’s algorithm A1
OR
Kruskal’s algorithm A1
[1 mark]
EITHER
using Prim’s algorithm, starting at A
A1A1A1A1A1
lowest cost road system contains roads AC, CD, CF, FE and AB A1
cost is 20 A1
OR
using Kruskal’s algorithm
A1A1A1A1A1
lowest cost road system contains roads CD, CF, FE, AC and AB A1
cost is 20 A1
Note: Accept alternative correct solutions.
[7 marks]