| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Standard +0.3 This is a standard application of Floyd's algorithm followed by routine algorithmic procedures (nearest neighbour for TSP). The question requires careful bookkeeping and systematic application of well-defined algorithms rather than problem-solving insight. While it involves multiple parts and Further Maths content (Decision Mathematics), the procedures are mechanical and would be familiar to students who have practiced these algorithms. Slightly above average difficulty due to the multi-step nature and potential for arithmetic errors, but fundamentally routine. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct application of Floyd's algorithm | M1 | sca Floyd |
| Correct distance matrix at each stage | A1 | distance |
| Correct route matrix at each stage | A1 | route |
| Second iteration correct | A1 | |
| Third iteration correct | A1 | |
| Fourth iteration — no change | A1 | no change |
| Circled element correct | A1 | |
| Remaining elements correct | A1 | |
| Final distance and route matrices correct | M1 A1 M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Distance \(= 4\) (row 1, col 3 of distance matrix) | B1 | |
| Route \(= 1, 2, 4, 3\) using \(1 \to r1c3 \to r2c3 \to r4c3\) of route matrix | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(1, 2, 4, 3, 1\) | B1 | |
| \(1, 2, 4, 3, 4, 2, 1\) | B1 | |
| Total distance \(= 8\) | B1 |
# Question 2:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct application of Floyd's algorithm | M1 | sca Floyd |
| Correct distance matrix at each stage | A1 | distance |
| Correct route matrix at each stage | A1 | route |
| Second iteration correct | A1 | |
| Third iteration correct | A1 | |
| Fourth iteration — no change | A1 | no change |
| Circled element correct | A1 | |
| Remaining elements correct | A1 | |
| Final distance and route matrices correct | M1 A1 M1 A1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Distance $= 4$ (row 1, col 3 of distance matrix) | B1 | |
| Route $= 1, 2, 4, 3$ using $1 \to r1c3 \to r2c3 \to r4c3$ of route matrix | M1 A1 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $1, 2, 4, 3, 1$ | B1 | |
| $1, 2, 4, 3, 4, 2, 1$ | B1 | |
| Total distance $= 8$ | B1 | |
---2 Answer this question on the insert provided.
Fig. 2 shows a network in which the weights on the arcs represent distances.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{9716cf3f-afa5-44a4-a8cd-f7511449d06b-2_405_497_1046_776}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
(i) Apply Floyd's algorithm on the insert provided to find the complete network of shortest distances.\\
(ii) Show how to use your final matrices to find the shortest route from vertex $\mathbf { 1 }$ to vertex 3, together with the length of that route.\\
(iii) Use the nearest neighbour algorithm, starting at vertex 1, to find a Hamilton cycle in the complete network of shortest distances.
Give the corresponding cycle in the original network, together with its length.
\hfill \mbox{\textit{OCR MEI D2 2006 Q2 [16]}}