| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2019 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with MST |
| Difficulty | Moderate -0.5 This is a straightforward application of three standard D1 algorithms (Dijkstra, Prim, Kruskal) with clear instructions and no novel problem-solving required. While it involves multiple parts and careful bookkeeping, each algorithm is routine and well-practiced. The question is slightly easier than average A-level maths because Decision Maths algorithms are largely procedural rather than requiring mathematical insight or proof. |
| 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 method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: ABDEFHKJ, Length: 76 (km) | M1 A1 A1ft A1 | a1M1: A larger value replaced by a smaller value in at least two of the working value boxes at either C or E or J or K. a1A1: All values in A, B, C, D and E correct and the working values in the correct order at C and E (including order of labelling). Condone lack of 0 in A's working value. a2A1: All values in F, G and H correct and the working values in the correct order. Penalise order of labelling only once per question (F, G and H must be labelled in that order and F must be labelled after A, B, C, D and E). Note that an additional working value of 56 at H after the 48 is not an error so 48 56 is fine, however, any other number or 56 48 in this order is incorrect and scores A0 in this part. a3A1ft: All values in K and J correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through K check that the working value at K follows from the candidate's final values from their feeds into K (which will come from nodes F, H and possibly even J (in the order in which the candidate has labelled them)) and that the final value, and order of |
| (b) Prim: AB, BC; BD, DE | M1; A1 | b1M1: First two arcs (AB, BC) chosen correctly in order, or first three nodes (ABC) chosen correctly in order. If any rejections seen at any point, or just a list of all the arcs in order, or only a list of weights then M0 (condone for M1only those who find the MST for the entire network). b1A1: CSO (must be considering arcs as must be AB, BC, BD, DE or BA, BC, etc.) – do not isw if candidates continue and find the MST for the entire network |
| (c) Kruskal: FG, JK, FH, not GH, HK, (not HJ), (not FK), (not GJ) | M1; A1 | c1M1: First two arcs (FG, JK) chosen correctly in order and at least one rejection seen at some point – no marks in this part if candidates apply Kruskal to the entire network or if only a list of weights given. c1A1: CSO – all selections and rejections correct in the correct order and at the correct time. Note that stating all the arcs in order (e.g. GF, JK, FH, GH, KH, JH, FK, GJ) and then stating only those in the tree in the correct order is fine for both marks in this part |
| (d) Total length: 85 (km) | B1 | d1B1: CAO (85) |
| Total: 11 marks |
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: ABDEFHKJ, Length: 76 (km) | M1 A1 A1ft A1 | a1M1: A larger value replaced by a smaller value in at least two of the working value boxes at either C or E or J or K. a1A1: All values in A, B, C, D and E correct and the working values in the correct order at C and E (including order of labelling). Condone lack of 0 in A's working value. a2A1: All values in F, G and H correct and the working values in the correct order. Penalise order of labelling only once per question (F, G and H must be labelled in that order and F must be labelled after A, B, C, D and E). Note that an additional working value of 56 at H after the 48 is not an error so 48 56 is fine, however, any other number or 56 48 in this order is incorrect and scores A0 in this part. a3A1ft: All values in K and J correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through K check that the working value at K follows from the candidate's final values from their feeds into K (which will come from nodes F, H and possibly even J (in the order in which the candidate has labelled them)) and that the final value, and order of |
| (b) Prim: AB, BC; BD, DE | M1; A1 | b1M1: First two arcs (AB, BC) chosen correctly in order, or first three nodes (ABC) chosen correctly in order. If any rejections seen at any point, or just a list of all the arcs in order, or only a list of weights then M0 (condone for M1only those who find the MST for the entire network). b1A1: CSO (must be considering arcs as must be AB, BC, BD, DE or BA, BC, etc.) – do not isw if candidates continue and find the MST for the entire network |
| (c) Kruskal: FG, JK, FH, not GH, HK, (not HJ), (not FK), (not GJ) | M1; A1 | c1M1: First two arcs (FG, JK) chosen correctly in order and at least one rejection seen at some point – no marks in this part if candidates apply Kruskal to the entire network or if only a list of weights given. c1A1: CSO – all selections and rejections correct in the correct order and at the correct time. Note that stating all the arcs in order (e.g. GF, JK, FH, GH, KH, JH, FK, GJ) and then stating only those in the tree in the correct order is fine for both marks in this part |
| (d) Total length: 85 (km) | B1 | d1B1: CAO (85) |
| **Total: 11 marks** | | |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-03_892_871_203_596}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents a network of roads between ten villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }$ and K . The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from A to J. State the route and its length.
During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
\item Use Prim's algorithm, starting at A , to find a minimum connector for the five villages $\mathrm { A } , \mathrm { B }$, C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
\item Use Kruskal's algorithm to find a minimum connector for the five villages $\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }$ and K . You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.
\item Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2019 Q2 [11]}}