| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Network construction from matrix |
| Difficulty | Moderate -0.8 This is a straightforward application of standard D1 algorithms: converting a distance matrix to a network diagram (routine skill) and applying Dijkstra's algorithm mechanically (well-practiced procedure with no conceptual challenges). Both parts require only direct recall and execution of learned techniques with no problem-solving insight needed. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.04a Shortest path: Dijkstra's algorithm |
| A | B | C | D | E | F | G | |
| A | - | 3 | 8 | - | 5 | - | - |
| B | 3 | - | 4 | - | - | - | 6 |
| C | 8 | 4 | - | 1 | 1 | - | 2 |
| D | - | - | 1 | - | - | - | 5 |
| E | 5 | - | 1 | - | - | 4 | - |
| F | - | - | - | - | 4 | - | 1 |
| G | - | 6 | 2 | 5 | - | 1 | - |
1 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 & - & 3 & 8 & - & 5 & - & - \\
\hline
B & 3 & - & 4 & - & - & - & 6 \\
\hline
C & 8 & 4 & - & 1 & 1 & - & 2 \\
\hline
D & - & - & 1 & - & - & - & 5 \\
\hline
E & 5 & - & 1 & - & - & 4 & - \\
\hline
F & - & - & - & - & 4 & - & 1 \\
\hline
G & - & 6 & 2 & 5 & - & 1 & - \\
\hline
\end{tabular}
\end{center}
(i) Draw the network.\\
(ii) Use Dijkstra's algorithm to find the shortest route from A to G . Give the route and its length.
\hfill \mbox{\textit{OCR MEI D1 2012 Q1 [8]}}