| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2024 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with different start/end |
| Difficulty | Standard +0.3 This is a standard D1 Chinese Postman problem with clearly defined steps: (a) routine Dijkstra's algorithm application, (b) standard odd-vertex pairing for route inspection with specified start/end, and (c) recognizing that optimal route occurs when start/end are the two odd vertices. All techniques are textbook procedures with no novel insight required, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Larger value replaced by smaller value in working values at nodes C, D, F, G, H, J | a1M1 | |
| All values at A, B, C, D, E correct with working values in correct order | a1A1 | |
| All values at F and G correct with working values in correct order | a2A1 | |
| All values at H and J correct on follow-through, working values in correct order | a3A1ft | Follow through from candidate's values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Shortest path: ABCDFGHJ | a4A1 | CAO |
| Length = 83 (km) | a5A1ft | Follow through their final value at J only if answer is 83 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B(CD)F + HJ = 30 + 5 = 35^*\) | b1M1 | Three distinct pairings of nodes B, F, H, J with one row correct |
| \(B(CDFG)H + F(GH)J = 61 + 36 = 97\) | b1A1 | Any two rows correct including pairings and totals |
| \(B(CDFGH)J + F(GH)J = 66 + 31 = 97\) | b2A1 | All three rows correct |
| Repeat arcs: BC, CD, DF and HJ | b3A1 | CAO - must be these arcs |
| Route length \(= 458 + 35 = 493\) (km) | b4A1ft | Correct or follow through their least repeat + 458 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Shortest path between any pair of the four odd nodes (A, B, F, H) is AB (17) | c1M1 | |
| Start at F and finish at H (or vice versa) | c1A1 | CAO (F, H) |
| Length \(= 458 + 17 = 475\) (km) | c1B1 | CAO (475) |
# Question 3 (Shortest Path / Route Inspection):
## Part (a)(i) - Dijkstra's Algorithm:
| Answer | Mark | Guidance |
|--------|------|----------|
| Larger value replaced by smaller value in working values at nodes C, D, F, G, H, J | a1M1 | |
| All values at A, B, C, D, E correct with working values in correct order | a1A1 | |
| All values at F and G correct with working values in correct order | a2A1 | |
| All values at H and J correct on follow-through, working values in correct order | a3A1ft | Follow through from candidate's values |
## Part (a)(ii) - Shortest Path:
| Answer | Mark | Guidance |
|--------|------|----------|
| Shortest path: ABCDFGHJ | a4A1 | CAO |
| Length = 83 (km) | a5A1ft | Follow through their final value at J only if answer is 83 |
## Part (b) - Route Inspection:
| Answer | Mark | Guidance |
|--------|------|----------|
| $B(CD)F + HJ = 30 + 5 = 35^*$ | b1M1 | Three distinct pairings of nodes B, F, H, J with one row correct |
| $B(CDFG)H + F(GH)J = 61 + 36 = 97$ | b1A1 | Any two rows correct including pairings and totals |
| $B(CDFGH)J + F(GH)J = 66 + 31 = 97$ | b2A1 | All three rows correct |
| Repeat arcs: BC, CD, DF and HJ | b3A1 | CAO - must be these arcs |
| Route length $= 458 + 35 = 493$ (km) | b4A1ft | Correct or follow through their least repeat + 458 |
## Part (c) - Start/Finish Points:
| Answer | Mark | Guidance |
|--------|------|----------|
| Shortest path between any pair of the four odd nodes (A, B, F, H) is AB (17) | c1M1 | |
| Start at F and finish at H (or vice versa) | c1A1 | CAO (F, H) |
| Length $= 458 + 17 = 475$ (km) | c1B1 | CAO (475) |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4814ebd7-f48a-49cf-8ca2-045d84abd63c-4_677_1100_212_479}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
[The total weight of the network is 458]
Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest path from A to J.
\item State the length of the shortest path from A to J .
The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
\end{enumerate}\item By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice.
If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
\item Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2024 Q3 [14]}}