| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Network construction from matrix |
| Difficulty | Moderate -0.3 This is a standard D1 question testing routine application of Dijkstra's algorithm and minimum spanning tree concepts. While multi-part with several marks, each part follows textbook procedures: reading a matrix, drawing networks, applying Dijkstra's algorithm mechanically, and applying Kruskal's/Prim's algorithm. Part (v) requires understanding why shortest path trees differ from MSTs, but this is a standard conceptual point. Slightly easier than average A-level due to being algorithmic rather than requiring problem-solving insight. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.02r Graph modelling: model and solve problems using graphs7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | |
| A | - | 5 | 2 | 3 | - | - | - |
| B | 5 | - | - | - | 1 | 1 | - |
| C | 2 | - | - | - | 4 | 1 | - |
| D | 3 | - | - | - | 4 | 2 | - |
| E | - | 1 | 4 | 4 | - | - | 1 |
| F | - | 1 | 1 | 2 | - | - | 5 |
| G | - | - | - | - | 1 | 5 | - |
4 The table defines a network in which the numbers represent lengths.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & 5 & 2 & 3 & - & - & - \\
\hline
B & 5 & - & - & - & 1 & 1 & - \\
\hline
C & 2 & - & - & - & 4 & 1 & - \\
\hline
D & 3 & - & - & - & 4 & 2 & - \\
\hline
E & - & 1 & 4 & 4 & - & - & 1 \\
\hline
F & - & 1 & 1 & 2 & - & - & 5 \\
\hline
G & - & - & - & - & 1 & 5 & - \\
\hline
\end{tabular}
\end{center}
(i) Draw the network.\\
(ii) Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.\\
(iii) Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.\\
(iv) Find a minimum connector for the original network, draw it, and give the total length of its edges.\\
(v) Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.
\hfill \mbox{\textit{OCR MEI D1 2012 Q4 [16]}}