| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with MST |
| Difficulty | Standard +0.3 This is a standard D1 question testing routine application of Dijkstra's and Kruskal's algorithms with straightforward follow-up questions. Parts (i)-(ii) are textbook algorithm applications, (iii)-(iv) require simple observation rather than re-computation, and (v) tests basic Eulerian path concepts. The multi-part structure and 8-mark allocation for part (i) indicate length rather than conceptual difficulty—all techniques are standard D1 content with no novel problem-solving required. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| (i) [Dijkstra's algorithm applied to network; labels shown; working values shown; starting at C] | B1 M1 A1 A1 A1 | starting at C Dijkstra labels order of labelling working values |
| B1 B1 B1 | ||
| (ii) PV ST CR RT UV TU QR; Length = 80 | M1 A1 A1 B1 | first 5 last 2 length |
| (iii) CP reduced to 26 CV reduced to 34 | B1 | both and no more |
| (iv) UV replaced by PQ; New length = 74 | B1 | |
| (v) Q Semi-Eulerian. (Order of P changed from 3 to 4, but order of Q changed from 2 to 3 – so still 2 odd vertices.) or Cross the bridge and proceed as before or A valid route | M1 A1 |
| (i) [Dijkstra's algorithm applied to network; labels shown; working values shown; starting at C] | B1 M1 A1 A1 A1 | starting at C Dijkstra labels order of labelling working values |
| | B1 B1 B1 | |
| (ii) PV ST CR RT UV TU QR; Length = 80 | M1 A1 A1 B1 | first 5 last 2 length |
| (iii) CP reduced to 26 CV reduced to 34 | B1 | both and no more |
| (iv) UV replaced by PQ; New length = 74 | B1 | |
| (v) Q Semi-Eulerian. (Order of P changed from 3 to 4, but order of Q changed from 2 to 3 – so still 2 odd vertices.) or Cross the bridge and proceed as before or A valid route | M1 A1 | |4 Answer parts (i) and (ii) on the insert provided.
Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-5_536_828_573_642}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{center}
\end{figure}
(i) Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]\\
(ii) Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector.
A bridge is built giving a direct road between P and Q of length 12 km .\\
(iii) What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)\\
(iv) What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)\\
(v) Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once.
Give this town and justify your answer.
\hfill \mbox{\textit{OCR MEI D1 2005 Q4 [16]}}