| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Moderate -0.5 Floyd's algorithm is a standard algorithmic procedure taught in D2 with clear mechanical steps. While it requires careful bookkeeping through multiple iterations and matrix updates, the question provides the final answer to verify against, reducing problem-solving demand. This is routine application of a learned algorithm rather than requiring insight or novel reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 22 | 14 | 11 | 23 |
| \(\mathbf { 2 }\) | 14 | 28 | 15 | 27 |
| \(\mathbf { 3 }\) | 11 | 15 | 22 | 12 |
| \(\mathbf { 4 }\) | 23 | 27 | 12 | 24 |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | 11 | 15 |
| 3 | 1 | 2 |
Question 3:
3 | 11 | 15 | 22 | 12
3 | 1 | 2 | 1 | 43 The weights on the network represent distances.\\
\includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-3_401_702_315_683}\\
(a) (i) Apply Floyd's algorithm to the network to find the complete network of shortest distances, showing that the final matrices are as follows.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ \\
\hline
$\mathbf { 1 }$ & 22 & 14 & 11 & 23 \\
\hline
$\mathbf { 2 }$ & 14 & 28 & 15 & 27 \\
\hline
$\mathbf { 3 }$ & 11 & 15 & 22 & 12 \\
\hline
$\mathbf { 4 }$ & 23 & 27 & 12 & 24 \\
\hline
\end{tabular}
\end{center}
\hfill \mbox{\textit{OCR MEI D2 2008 Q3 [20]}}