| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a routine application of standard algorithms (Prim's and Dijkstra's) from Decision Mathematics 1, requiring only mechanical execution of learned procedures on a small network with no problem-solving or insight needed. The question explicitly tells students which algorithms to use and asks for straightforward description, making it easier than average A-level questions which typically require some independent thinking. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method |
6 The diagram shows routes between points in a town. The distances are in kilometres.\\
\includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-6_817_1219_319_422}\\
(i) Use an appropriate algorithm to find a set of connecting arcs of minimum total length. Indicate your connecting arcs on the copy of the diagram in your answer book, and give their total length.\\
(ii) Give the name of the algorithm you have used, and describe it briefly.\\
(iii) Using the second diagram in your answer book, apply Dijkstra's algorithm to find the shortest distances from A to each of the other points.
List the connections that are used, and give their total length.
\hfill \mbox{\textit{OCR MEI D1 2008 Q6 [16]}}