EXM.1.AHL.TZ0.37
In this part, marks will only be awarded if you show the correct application of the required algorithms, and show all your working.
In an offshore drilling site for a large oil company, the distances between the planned wells are given below in metres.
It is intended to construct a network of paths to connect the different wells in a way that minimises the sum of the distances between them.
Use Prim’s algorithm, starting at vertex 3, to find a network of paths of minimum total length that can span the whole site.
Markscheme / solution
(R2)(A4)(M1)
(A1)
Note: Award (R2) for correct algorithms, (R1) for 1 error, (R0) for 2 or more errors.
Award (A4) for correct calculations, (A3) for 1 error, (A2) for 2 errors, (A1) for 3 errors, (A0) for 4 or more errors.
Award (M1) for tree/table/method.
Award (A1) for minimum weight.
[8 marks]