| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2016 |
| Session | June |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.8 This is a substantial multi-part Floyd's algorithm question requiring four iterations, route extraction, network drawing, and application of TSP algorithms (nearest neighbour and lower bound). While the individual techniques are standard D2 content, the question demands careful execution across multiple parts with opportunities for error propagation, and the interpretation back to the original network adds conceptual depth beyond routine application. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) |
| \(\mathbf { 1 }\) | - | 13 | 14 | 11 | 15 |
| \(\mathbf { 2 }\) | 13 | - | 19 | 20 | 22 |
| \(\mathbf { 3 }\) | 14 | 19 | - | 10 | 17 |
| \(\mathbf { 4 }\) | 11 | 20 | 10 | - | 13 |
| \(\mathbf { 5 }\) | 15 | 16 | 12 | 14 | 24 |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) |
| \(\mathbf { 1 }\) | 2 | 2 | 2 | 4 | 5 |
| \(\mathbf { 2 }\) | 1 | 3 | 3 | 3 | 3 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 4 | 5 |
| \(\mathbf { 4 }\) | 1 | 3 | 3 | 3 | 5 |
| \(\mathbf { 5 }\) | 1 | 3 | 3 | 4 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| - A header with numbers (5 | 15 | 16 |
I cannot clean up this content as requested because what you've provided does not contain actual marking scheme information with marking points (M1, A1, B1, DM1, etc) and their associated guidance.
The text you've shared appears to be:
- A header with numbers (5 | 15 | 16 | 12 | 14 | 24 and 1 | 2 | 3 | 4 | 5)
- Copyright information from OCR
To help you effectively, please provide the actual mark scheme content that includes the marking criteria and points to be cleaned up.\begin{center}
\begin{tabular}{ | l | l | l | l | l | l | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ & $\mathbf { 5 }$ \\
\hline
$\mathbf { 1 }$ & - & 13 & 14 & 11 & 15 \\
\hline
$\mathbf { 2 }$ & 13 & - & 19 & 20 & 22 \\
\hline
$\mathbf { 3 }$ & 14 & 19 & - & 10 & 17 \\
\hline
$\mathbf { 4 }$ & 11 & 20 & 10 & - & 13 \\
\hline
$\mathbf { 5 }$ & 15 & 16 & 12 & 14 & 24 \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | l | l | l | l | l | l | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ & $\mathbf { 5 }$ \\
\hline
$\mathbf { 1 }$ & 2 & 2 & 2 & 4 & 5 \\
\hline
$\mathbf { 2 }$ & 1 & 3 & 3 & 3 & 3 \\
\hline
$\mathbf { 3 }$ & 2 & 2 & 2 & 4 & 5 \\
\hline
$\mathbf { 4 }$ & 1 & 3 & 3 & 3 & 5 \\
\hline
$\mathbf { 5 }$ & 1 & 3 & 3 & 4 & 3 \\
\hline
\end{tabular}
\end{center}
(i) Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.\\
(ii) Show how to use the matrices to give the shortest distance and the shortest route from vertex $\mathbf { 1 }$ to vertex 2.\\
(iii) Draw the complete network of shortest distances.\\
(iv) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.\\
(v) By temporarily deleting vertex $\mathbf { 1 }$ and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
\hfill \mbox{\textit{OCR MEI D2 2016 Q5}}