| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| 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 requiring routine application of two well-practiced algorithms (Dijkstra and Kruskal) with straightforward working. Part (iv) adds mild problem-solving by asking students to work backwards, but the logic is direct: compare current shortest path/MST with alternatives including AD. Slightly easier than average A-level maths due to being algorithmic rather than requiring mathematical insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | - | 22 | - | 12 | 10 | - |
| B | 22 | - | - | - | - | 13 |
| C | - | - | - | 6 | 5 | 11 |
| D | 12 | - | 6 | - | - | - |
| E | 10 | - | 5 | - | - | 26 |
| F | - | 13 | 11 | - | 26 | - |
| Answer | Marks | Guidance |
|---|---|---|
| (i) & (ii) Shortest route: AECF, Distance: 26 miles | M1 A1 A1 | network arcs lengths; Dijkstra working values; order of labelling labels |
| (iii) CE CD AE CF AD BF AB EF | M1 | 5 arc connector |
| A1 | AD not included | |
| A1 | all OK, inc order | |
| Total length of connector = 45 | B1 | |
| (iv) A: 3 miles (or length = 9) | B1 | |
| B: 2 miles (or length = 10) | B1 |
**(i) & (ii)** Shortest route: AECF, Distance: 26 miles | M1 A1 A1 | network arcs lengths; Dijkstra working values; order of labelling labels
**(iii)** CE CD AE CF AD BF AB EF | M1 | 5 arc connector
| A1 | AD not included
| A1 | all OK, inc order
Total length of connector = 45 | B1 |
**(iv)** A: 3 miles (or length = 9) | B1 |
B: 2 miles (or length = 10) | B1 |5 The matrix shows the distances in miles between towns where direct routes exist.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 22 & - & 12 & 10 & - \\
\hline
B & 22 & - & - & - & - & 13 \\
\hline
C & - & - & - & 6 & 5 & 11 \\
\hline
D & 12 & - & 6 & - & - & - \\
\hline
E & 10 & - & 5 & - & - & 26 \\
\hline
F & - & 13 & 11 & - & 26 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Draw the network.
\item Use Dijkstra's algorithm to find the shortest route from A to F . Give the route and its length.
\item Use Kruskal's algorithm to find a minimum connector for the network, showing your working. Draw your connector and give its total length.
\item How much shorter would AD have to be if it were to be included in\\
(A) a shortest route from A to F ,\\
(B) a minimum connector?
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2010 Q5 [16]}}