| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with MST |
| Difficulty | Standard +0.3 This is a straightforward application of standard D1 algorithms (Dijkstra, Kruskal, Prim) with clear instructions and no novel problem-solving required. The question is structured as routine textbook exercises with multiple parts guiding students through each algorithm step-by-step. While it requires careful execution and understanding of three algorithms, these are core D1 content practiced extensively, making this easier than average for A-level maths overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied: E correct | B1 | Dijkstra – E correct |
| Other working values correct | B1 | other working values |
| Order of labelling correct | B1 | order of labelling |
| Labels correct | B1 | labels |
| Route: A D C Z U W X or A B D C Z U W X | B1 | |
| Distance: 48 km | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| No difference (allow "one fewer"), as 15 (CZ) does not need to be added to determine the route | M1 | Need comment re just one arc connecting the two networks |
| Part (i) is effectively using Dijkstra on left network then Dijkstra on right network, but starting at 30 instead of 0 on the right network | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Order of choice: AB, \(BD \leftrightarrow DE\), DC, EF | M1 | Kruskal (first 2 arcs identified – OK if by length) |
| Correct minimum spanning tree diagram (A-B-C-D-E-F with given weights) | A1 | |
| Minimum connector identified | B1 | min connector |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Order of inclusion: U, W, X, \(V \leftrightarrow Y\), Z | M1 | Prim (first 2 vertices identified - OK to say UW, WX, etc., but in that order. Not OK to identify by lengths) |
| Correct minimum spanning tree diagram (U-V-W-X-Y-Z with given weights) | A1 | |
| Minimum connector identified | B1 | min connector |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total length \(= 72\) km | B1cao | \(27 + 30\) |
| B1 | \(+ 15\) for the pass |
# Question 6:
## Part (a)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied: E correct | B1 | Dijkstra – E correct |
| Other working values correct | B1 | other working values |
| Order of labelling correct | B1 | order of labelling |
| Labels correct | B1 | labels |
| Route: A D C Z U W X or A B D C Z U W X | B1 | |
| Distance: 48 km | B1 | |
## Part (a)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| No difference (allow "one fewer"), as 15 (CZ) does not need to be added to determine the route | M1 | Need comment re just one arc connecting the two networks |
| Part (i) is effectively using Dijkstra on left network then Dijkstra on right network, but starting at 30 instead of 0 on the right network | A1 | |
## Part (b)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Order of choice: AB, $BD \leftrightarrow DE$, DC, EF | M1 | Kruskal (first 2 arcs identified – OK if by length) |
| Correct minimum spanning tree diagram (A-B-C-D-E-F with given weights) | A1 | |
| Minimum connector identified | B1 | min connector |
## Part (b)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Order of inclusion: U, W, X, $V \leftrightarrow Y$, Z | M1 | Prim (first 2 vertices identified - OK to say UW, WX, etc., but in that order. Not OK to identify by lengths) |
| Correct minimum spanning tree diagram (U-V-W-X-Y-Z with given weights) | A1 | |
| Minimum connector identified | B1 | min connector |
## Part (b)(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total length $= 72$ km | B1cao | $27 + 30$ |
| | B1 | $+ 15$ for the pass |6 A mountain ridge separates two populated areas. Networks representing roads connecting the villages in each area are shown below. The numbers on the arcs represent distances in kilometres.\\
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-7_524_1429_340_319}
There is also a mountain road of length 15 kilometres connecting C to Z .
\begin{enumerate}[label=(\alph*)]
\item A national bus company needs a route from A to X .
\begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the complete network, including CZ, to find the shortest route from A to X . Give the route and its corresponding distance.
\item Would it need fewer computations to use Dijkstra's algorithm on the network for villages A to F to find the shortest route from A to C, and then use Dijkstra's algorithm on the network for villages U to Z to find the shortest route from Z to X? Give a brief justification for your answer.
\end{enumerate}\item The local council needs to discover which roads it should keep clear of snow during the winter to keep all the villages connected, and the corresponding total length of road.
\begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm on the network for villages A to F to find a minimum connector for $\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } \}$. Show your use of the algorithm. Draw your minimum connector.
\item Use Prim's algorithm on the network for villages U to Z to find a minimum connector for $\{ \mathrm { U } , \mathrm { V } , \mathrm { W } , \mathrm { X } , \mathrm { Y } , \mathrm { Z } \}$, starting at U . Show your use of the algorithm. Draw your minimum connector.
\item What is the total length of road that the council must keep clear of snow?
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2016 Q6 [16]}}