OCR MEI D1 2008 January — Question 6

Exam BoardOCR MEI
ModuleD1 (Decision Mathematics 1)
Year2008
SessionJanuary
TopicMinimum Spanning Trees

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}
  1. 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.
  2. Give the name of the algorithm you have used, and describe it briefly.
  3. 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.