| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2024 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.5 This is a standard D1 question testing routine application of Prim's algorithm and Chinese Postman problem concepts. Part (a) requires mechanical application of Prim's to a distance table, (b) is trivial addition, (c) requires identifying odd-degree vertices and pairing them (standard textbook exercise), and (d) extends this slightly. While multi-part with several marks, it requires no novel insight—just careful execution of learned algorithms. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | H | J | |
| A | - | 15 | 7 | 25 | 15 | 42 | 64 | 51 | 46 |
| B | 15 | - | 22 | 40 | 30 | 57 | 49 | 36 | 31 |
| C | 7 | 22 | - | 32 | 22 | 49 | 71 | 58 | 53 |
| D | 25 | 40 | 32 | - | 10 | 17 | 57 | 70 | 71 |
| E | 15 | 30 | 22 | 10 | - | 27 | 67 | 66 | 61 |
| F | 42 | 57 | 49 | 17 | 27 | - | 40 | 53 | 72 |
| G | 64 | 49 | 71 | 57 | 67 | 40 | - | 13 | 32 |
| H | 51 | 36 | 58 | 70 | 66 | 53 | 13 | - | 19 |
| J | 46 | 31 | 53 | 71 | 61 | 72 | 32 | 19 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Part | Answer/Working | Marks |
| 4(a) | Prim: AC, AB, AE; DE, DF, BJ; HJ, GH or AC, AE, DE; AB, DF, BJ; HJ, GH | M1 A1 A1 (3) |
| 4(b) | 127 (km) | B1 (1) |
| 4(c) | If starting at E and finishing at F then the shortest path between C and H needs to be traversed twice. So the length of the route is \(58 + 494 = 552\) (km) | M1 A1 (2) |
| 4(d) | Route must start C and finish at A therefore need to consider pairings of the nodes A, E, F and H; \(AE + FH = 15 + 53 = 68\); \(AF + EH = 42 + 66 = 108\); \(AH + EF = 51 + 27 = 78\) | M1, A1, A1 (4) |
| Repeat roads: AE, FG, GH | A1 | |
| Special Case – considers C, E, F and H – mark as misread removing final 2 A marks earned in this section | M1 | \(CE + FH = 22 + 53 = 75\); \(CF + EH = 49 + 66 = 115\); \(CH + EF = 58 + 27 = 85\); Repeat roads: CA, AE, FG, GH |
| 4(e) | \(B - A - C - E - D - F - G - H - J - B\); \(15 + 7 + 22 + 10 + 17 + 40 + 13 + 19 + 31 = 174\) (km) | M1, A1 (2) |
| 4(f) | \((127 - 7) + 7 + 22 = 149\) (km) | M1 A1 (2) |
| Total: 14 marks |
| Part | Answer/Working | Marks | Guidance |
|------|---|---|---|
| 4(a) | Prim: AC, AB, AE; DE, DF, BJ; HJ, GH or AC, AE, DE; AB, DF, BJ; HJ, GH | M1 A1 A1 (3) | Prim's – first three arcs correctly chosen in order (AC, AB, AE, ... or AC, AE, DE) or first four nodes {A, C, B, E, ... or A, C, E, D,...} correctly chosen in order. If any explicit rejections seen at some point then M1 (max) only. Order of nodes may be seen at the top of a matrix/table {1, 3, 2, -, 4, -, -, -, or 1, -, 2, 4, 3, -, -, -, -}. Starting at any other node can score M1 only for first three arcs chosen correctly. First six arcs correctly chosen in order {AC, AB, AE, DE, DF, BJ, ...} or all nine nodes {A, C, B, E, D, F, J, H, G} correctly chosen in order. Order of nodes may be seen at the top of a matrix so for the first two marks accept {1, 3, 2, 5, 4, 6, 9, 8, 7} (no missing numbers). Or the alternative six arcs {AC, AE, DE; AB, DF, BJ, ...} nine nodes {A, C, E, D, B, F, J, H, G} or numbers {1, 3, -, 2, 4, 6, 9, 8, 7}. CSO – all arcs correctly stated and chosen in the correct order (with no additional arcs). They must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen) |
| 4(b) | 127 (km) | B1 (1) | CAO (127) |
| 4(c) | If starting at E and finishing at F then the shortest path between C and H needs to be traversed twice. So the length of the route is $58 + 494 = 552$ (km) | M1 A1 (2) | Indication that the shortest path between C and H needs to be traversed twice (correct answer can imply this mark) |
| 4(d) | Route must start C and finish at A therefore need to consider pairings of the nodes A, E, F and H; $AE + FH = 15 + 53 = 68$; $AF + EH = 42 + 66 = 108$; $AH + EF = 51 + 27 = 78$ | M1, A1, A1 (4) | |
| | Repeat roads: AE, FG, GH | A1 | |
| | **Special Case – considers C, E, F and H – mark as misread removing final 2 A marks earned in this section** | M1 | $CE + FH = 22 + 53 = 75$; $CF + EH = 49 + 66 = 115$; $CH + EF = 58 + 27 = 85$; Repeat roads: CA, AE, FG, GH |
| 4(e) | $B - A - C - E - D - F - G - H - J - B$; $15 + 7 + 22 + 10 + 17 + 40 + 13 + 19 + 31 = 174$ (km) | M1, A1 (2) | |
| 4(f) | $(127 - 7) + 7 + 22 = 149$ (km) | M1 A1 (2) | |
| | **Total: 14 marks** | | |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-06_873_1620_242_223}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
[The total weight of the network is 494]\\
Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3.
The number on each arc represents the lengths, in kilometres, of the corresponding road.\\
The table below shows the shortest distances, in kilometres, between the nine factories.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G & H & J \\
\hline
A & - & 15 & 7 & 25 & 15 & 42 & 64 & 51 & 46 \\
\hline
B & 15 & - & 22 & 40 & 30 & 57 & 49 & 36 & 31 \\
\hline
C & 7 & 22 & - & 32 & 22 & 49 & 71 & 58 & 53 \\
\hline
D & 25 & 40 & 32 & - & 10 & 17 & 57 & 70 & 71 \\
\hline
E & 15 & 30 & 22 & 10 & - & 27 & 67 & 66 & 61 \\
\hline
F & 42 & 57 & 49 & 17 & 27 & - & 40 & 53 & 72 \\
\hline
G & 64 & 49 & 71 & 57 & 67 & 40 & - & 13 & 32 \\
\hline
H & 51 & 36 & 58 & 70 & 66 & 53 & 13 & - & 19 \\
\hline
J & 46 & 31 & 53 & 71 & 61 & 72 & 32 & 19 & - \\
\hline
\end{tabular}
\end{center}
\section*{Table of shortest distances}
\begin{enumerate}[label=(\alph*)]
\item Starting at A, use Prim's algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.\\
(3)
\item State the weight of the minimum spanning tree.\\
(1)
A route is needed that minimises the total distance to traverse each road at least once. The route must start at E and finish at F .
\item Determine the length of this route. You must give a reason for your answer.
It is now decided to start the route at C and finish the route at A . The route must include every road at least once and must still minimise the total distance travelled.
\item By considering the pairings of all relevant nodes, find the roads that need to be traversed twice.
Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.
\item Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko's route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.
\item By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko's route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2024 Q4 [14]}}