| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.3 This is a standard Floyd's algorithm question requiring mechanical execution of the fourth iteration, route extraction from a routing matrix, drawing a network, and applying nearest neighbour algorithm. While multi-part with several marks, each step follows algorithmic procedures taught directly in D2 with no novel problem-solving or insight required—slightly easier than average due to its purely procedural nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) |
| \(\mathbf { 1 }\) | 0 | 9 | 20 | 11 | 15 |
| \(\mathbf { 2 }\) | 9 | 0 | 11 | 20 | 24 |
| \(\mathbf { 3 }\) | 20 | 11 | 0 | 9 | 13 |
| \(\mathbf { 4 }\) | 11 | 20 | 9 | 0 | 4 |
| \(\mathbf { 5 }\) | 15 | 24 | 13 | 4 | 0 |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) |
| \(\mathbf { 1 }\) | 1 | 2 | 2 | 4 | 4 |
| \(\mathbf { 2 }\) | 1 | 2 | 3 | 3 | 3 |
| \(\mathbf { 3 }\) | 2 | 2 | 3 | 4 | 4 |
| \(\mathbf { 4 }\) | 1 | 1 | 3 | 4 | 5 |
| \(\mathbf { 5 }\) | 15 | 23 | 43 | 16 | 30 |
| \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 | 1 | 3 | 4 | 5 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 2 | 2 |
| \(\mathbf { 4 }\) | 1 | 2 | 2 | 2 | 5 |
| \(\mathbf { 5 }\) | 1 | 2 | 2 | 4 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | 15 | 23 |
| 1 | 2 | 3 |
| 5 | 1 | 2 |
Question 5:
5 | 15 | 23 | 43 | 16 | 30
1 | 2 | 3 | 4 | 5
5 | 1 | 2 | 2 | 4 | 1\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 }$ & 0 & 9 & 20 & 11 & 15 \\
\hline
$\mathbf { 2 }$ & 9 & 0 & 11 & 20 & 24 \\
\hline
$\mathbf { 3 }$ & 20 & 11 & 0 & 9 & 13 \\
\hline
$\mathbf { 4 }$ & 11 & 20 & 9 & 0 & 4 \\
\hline
$\mathbf { 5 }$ & 15 & 24 & 13 & 4 & 0 \\
\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 }$ & 1 & 2 & 2 & 4 & 4 \\
\hline
$\mathbf { 2 }$ & 1 & 2 & 3 & 3 & 3 \\
\hline
$\mathbf { 3 }$ & 2 & 2 & 3 & 4 & 4 \\
\hline
$\mathbf { 4 }$ & 1 & 1 & 3 & 4 & 5 \\
\hline
$\mathbf { 5 }$ & 15 & 23 & 43 & 16 & 30 \\
\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 & 1 & 3 & 4 & 5 \\
\hline
$\mathbf { 3 }$ & 2 & 2 & 2 & 2 & 2 \\
\hline
$\mathbf { 4 }$ & 1 & 2 & 2 & 2 & 5 \\
\hline
$\mathbf { 5 }$ & 1 & 2 & 2 & 4 & 1 \\
\hline
\end{tabular}
\end{center}
(ii) Perform the fourth iteration.
There are no changes on the fifth iteration, so your answer to part (ii) should give the complete network of shortest distances.\\
(iii) Use your matrices to find the shortest distance and route from vertex $\mathbf { 3 }$ to vertex $\mathbf { 1 }$, and explain how you do it.\\
(iv) Draw the complete network of shortest distances, not including the loops.\\
(v) Apply the nearest neighbour algorithm to your network in part (iv), starting at vertex 2. Give the length of the Hamilton cycle that is produced.
Interpret the Hamilton cycle in terms of the original diagram and state what the algorithm has achieved.
}{www.ocr.org.uk}) after the live examination series.\\
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.\\
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1PB.\\
OCR is part of the
\hfill \mbox{\textit{OCR MEI D2 2009 Q5}}