| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | June |
| Marks | 18 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Combined Dijkstra and route inspection |
| Difficulty | Standard +0.8 This is a substantial multi-part question combining Dijkstra's algorithm with route inspection (Chinese Postman Problem), requiring students to apply algorithms systematically, adapt to constraints (via A, start/finish at G, roads closed), and analyze odd vertices. While the individual algorithms are standard D1 content, the length, multiple parts, and need to modify the network in part (e) elevate this above a typical textbook exercise. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Dijkstra's algorithm applied correctly | M1 | Larger value replaced by smaller at least once in working values at C, F, D, H or J |
| Correct values at B, E, C, F and working values in correct order at C | A1 (BECF) | All values correct with correct order of labelling |
| Correct values at G and D with working values in correct order | A1 (GD) | G and D labelled in that order, after B, E, C, F |
| Correct values at H and J with working values in correct order | A1ft (HJ) | Follow through on final values from E, F, G and D |
| Shortest time: 58 mins | A1ft | Follow through on final value at J |
| Quickest route: \(A-E-G-H-J\) | A1 | CAO, route A to J or J to A |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Route D to H via A: \(D-F-C-B-A-E-G-H\) | B1 | CAO, correct route from D to H via A |
| Length: 101 mins | B1ft | Follow through on final value at \(D\) + final value at \(H\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(A(BCF)D + F(D)J = 46 + 25 = 71\) | M1 A1 | Three distinct pairings of A, D, F and J; any row correct including pairing and total |
| \(A(EGH)J + DF = 58 + 12 = 70\) | A1 | Any two rows correct including pairings and totals |
| \(A(BC)F + DJ = 34 + 13 = 47^*\) | A1 | All three rows correct including pairings and totals |
| Arcs AB, BC, CF and DJ will be traversed twice | A1 | CAO correct edges clearly stated; do not accept AF or AF via B and C |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Route: GHEFHJDJFCFDCBCABAEG | B1 | Any correct route in terms of vertices or arcs; starts/finishes at G, 20 vertices |
| Length: \(275 + 47 = 322\) mins | B1ft | \(275 +\) smallest repeat from (c); dependent on M mark in (c) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Start at D, finish at J (or vice-versa) or start at C, finish at J (or vice-versa) | M1 A1 | Any consideration of odd nodes (C, D, F, J) or arcs CF and DF; must clearly choose starting/finishing points |
| Length: \(275 - 12 - 10 + 12 = 265\) mins | B1 | CAO (265) |
# Question 4:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly | M1 | Larger value replaced by smaller at least once in working values at C, F, D, H or J |
| Correct values at B, E, C, F and working values in correct order at C | A1 (BECF) | All values correct with correct order of labelling |
| Correct values at G and D with working values in correct order | A1 (GD) | G and D labelled in that order, after B, E, C, F |
| Correct values at H and J with working values in correct order | A1ft (HJ) | Follow through on final values from E, F, G and D |
| Shortest time: 58 mins | A1ft | Follow through on final value at J |
| Quickest route: $A-E-G-H-J$ | A1 | CAO, route A to J or J to A |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Route D to H via A: $D-F-C-B-A-E-G-H$ | B1 | CAO, correct route from D to H via A |
| Length: 101 mins | B1ft | Follow through on final value at $D$ + final value at $H$ |
## Part (c)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $A(BCF)D + F(D)J = 46 + 25 = 71$ | M1 A1 | Three distinct pairings of A, D, F and J; any row correct including pairing and total |
| $A(EGH)J + DF = 58 + 12 = 70$ | A1 | Any two rows correct including pairings and totals |
| $A(BC)F + DJ = 34 + 13 = 47^*$ | A1 | All three rows correct including pairings and totals |
| Arcs AB, BC, CF and DJ will be traversed twice | A1 | CAO correct edges clearly stated; do not accept AF or AF via B and C |
## Part (d)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Route: GHEFHJDJFCFDCBCABAEG | B1 | Any correct route in terms of vertices or arcs; starts/finishes at G, 20 vertices |
| Length: $275 + 47 = 322$ mins | B1ft | $275 +$ smallest repeat from (c); dependent on M mark in (c) |
## Part (e)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Start at D, finish at J (or vice-versa) **or** start at C, finish at J (or vice-versa) | M1 A1 | Any consideration of odd nodes (C, D, F, J) or arcs CF and DF; must clearly choose starting/finishing points |
| Length: $275 - 12 - 10 + 12 = 265$ mins | B1 | CAO (265) |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-05_876_1353_230_354}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
[The total weight of the network is 275]\\
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route.
On Monday, Mandeep must travel from D to H via A.
\item Find the shortest time needed to travel from D to H via A . State the quickest route.
On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
\item Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
\item Write down a possible route, giving its duration.
On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
\item State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q4 [18]}}