| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.3 This is a multi-part question testing standard D2 algorithms (Floyd's, nearest neighbour, Prim's) with straightforward application. While it has many parts (7 total), each involves routine algorithmic procedures or direct reading from given matrices. The extension to 5 nodes in part (iii) explicitly states no algorithm is required, and parts (v)-(vii) are standard textbook applications. The question is slightly easier than average A-level maths due to its algorithmic/procedural nature requiring minimal problem-solving insight. |
| 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 method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | 2 | 3 |
| 3 | 10 | 7 |
| 3 | 2 | 2 |
| 3 | 11 | 15 |
| 3 | 1 | 2 |
| 3 | 42 | 20 |
| 3 | 2 | 2 |
| 3 | ∞ | 6 |
| 3 | 1 | 2 |
| 3 | 18 | 5 |
| 3 | 4 | 4 |
Question 3:
3
3 Floyd’s algorithm is applied to the following network:
1 3 2
2
8 7
4 1 3
At the end of the third iteration of the algorithm the distance and route matrices are as follows:
1 2 3 4 1 2 3 4
1 6 3 10 5 1 2 2 2 2
2 3 6 7 2 2 1 1 3 4
3 10 7 14 1 3 2 2 2 4
4 5 2 1 2 4 2 2 3 3
(i) Perform the fourth (final) iteration of the algorithm. [7]
(ii) Explain how to use the final matrices to find the shortest distance and the shortest route from
vertex 1 to vertex 3, and give the distance and route. [4]
(iii) Draw the complete network of shortest distances. [1]
(iv) Apply the nearest neighbour algorithm, starting at vertex 1, to your complete network of
shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route
through the original network. [3]
(v) By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to
the travelling salesperson problem in the original network. [3]
(vi) Explain what you can deduce from your answers to parts (iv) and (v). [2]
[Question 4 is printed overleaf.]
[Turn over
© OCR 2007 4772/01 June 07
1 | 2 | 3 | 4
3 | 10 | 7 | 14 | 1
3 | 2 | 2 | 2 | 4
3 | 11 | 15 | 22 | 12
3 | 1 | 2 | 1 | 4
3 | 42 | 20 | 40 | 25 | 43
3 | 2 | 2 | 2 | 2 | 2
3 | ∞ | 6 | ∞ | 3 | ∞ | ∞
3 | 1 | 2 | 3 | 4 | 5 | 6
3 | 18 | 5 | 6 | 3 | 11 | 19
3 | 4 | 4 | 4 | 4 | 4 | 4The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2.
\includegraphics{figure_3}
\includegraphics{figure_4}
\begin{enumerate}[label=(\roman*)]
\item Draw the complete network of shortest distances. [2]
\item Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. [2]
\end{enumerate}
A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3.
\includegraphics{figure_5}
\begin{enumerate}[label=(\roman*), start=3]
\item Draw the extended network and the complete 5-node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.) [3]
\item Produce the shortest distance matrix and the route matrix for the extended 5-node network. [3]
\item Apply the nearest neighbour algorithm to your $5 \times 5$ distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network. [3]
\item By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm. [4]
\item In the original 5-node network find a shortest route starting at vertex 1 and using each of the 6 arcs at least once. Give the length of your route. [3]
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D2 Q3 [20]}}