| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | Specimen |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Moderate -0.5 This is a standard D1 question testing routine application of two algorithms (Dijkstra's and route inspection). Part (a) is textbook Dijkstra's with no complications, part (b) is trivial addition, and part (c) follows the standard route inspection procedure. While it requires careful execution across 15 marks, it demands no problem-solving insight—just methodical application of learned algorithms, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| [Dijkstra's algorithm diagram showing working values at nodes] | M1, A1 (JEFD), A1 (BG), A1ft (HK) |
| Quickest route: A – G – H – K | A1 |
| Shortest time: 32 (mins) | A1ft |
| (6) |
| Answer | Marks | Guidance |
|---|---|---|
| Length: 51 (mins) | B1, B1ft | cao (BDEAGHK); 51 or their final value at B + their final value at K (condone lack of units) |
| (2) |
| Answer | Marks |
|---|---|
| A(G)H + B(DE)F = 29 + 11 = 40 | M1, A1ft, A1ft, A1ft |
| Answer | Marks |
|---|---|
| Route length = 196 + 34 = 230 (mins) | A1A1, A1 |
| (7) |
## 4(a)
[Dijkstra's algorithm diagram showing working values at nodes] | M1, A1 (JEFD), A1 (BG), A1ft (HK) |
Quickest route: A – G – H – K | A1 |
Shortest time: 32 (mins) | A1ft |
| | (6) |
A larger value replaced by a smaller value at least once in the working values at either B or H or K. All values in J, E, F and D correct and the working values in the correct order. Penalise order of labelling only once per question. Condone an additional working value at F of 22. All values in B and G correct and the working values in the correct order. Penalise order of labelling only once per question (B and G must be labelled in that order and B must be labelled after J, E, F, D). Condone an additional working value of 20 at B and an additional working value of 26 at G. All values in H and K correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question (H and K must be labelled in that order and H labelled after all other nodes (excluding K)). CAO (AGHK). Follow through on their final value at K – if their answer is not 32 follow through their final value at K (condone lack of units)
## 4(b)
Route from B to K via A: B – D – E – A – G – H – K
Length: 51 (mins) | B1, B1ft | cao (BDEAGHK); 51 or their final value at B + their final value at K (condone lack of units)
| | (2) |
## 4(c)
A(ED)B + F(G)H = 19 + 15 = 34
AF + B(K)H = 16 + 18 = 34
A(G)H + B(DE)F = 29 + 11 = 40 | M1, A1ft, A1ft, A1ft |
Arcs AF, BK, KH or AE, ED, DB, FG, GH will be traversed twice
Route length = 196 + 34 = 230 (mins) | A1A1, A1 |
| | (7) |
Three distinct pairings of the correct four odd nodes. One row correct including pairing and total (the ft on the first three A marks in (c) is for using their final values at B, F and H from (a) for the lengths of AB, AF and AH only). Two rows correct including pairing and totals. All three rows correct including pairing and totals. cao one combination of arcs that need traversing twice (arcs must be explicitly stated and not implied by working). cao both combination of arcs that need traversing twice (arcs must be explicitly stated and not implied by working). cao (230)
---\includegraphics{figure_1}
Figure 1 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest time needed to travel from A to K. State the quickest route. \hfill [6]
\end{enumerate}
On a particular day Oliver must travel from B to K via A.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Find a route of minimal time from B to K that includes A, and state its length. \hfill [2]
\end{enumerate}
Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear. \hfill [7]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q4 [15]}}