| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | January |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.3 This is a standard D1 Dijkstra's algorithm question with routine extensions. Part (a) is textbook application of the algorithm, part (b) requires simple path concatenation, and part (c) is standard route inspection. All parts follow well-practiced 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 |
|---|---|---|
| (a) | Network diagram shown with nodes and arcs labeled with times. Early event times shown in boxes. | M1 A1 (JEFD) A1 (BG) A1ft (HK) |
| (b) | Quickest route: A – G – H – K. Shortest time: 32 (mins). Route from B to K via A: B – D – E – A – G – H – K. Length: 51 (mins) | A1 A1ft B1 B1ft |
| (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\). Arcs AF, BK, KH or AE, ED, DB, FG, GH will be traversed twice. Route length = \(196 + 34 = 230\) (mins) | M1 A1 A1 A1 A1 A1ft |
| Answer | Marks |
|---|---|
| a1M1 | A larger value replaced by a smaller value at least once at B or H or K. |
| a1A1 | All values in J, F, E and D correct. |
| a2A1 | All values in B and G correct. |
| a3A1ft | All values in H and K correct on the follow through. |
| a4A1 | Cao (shortest path) |
| a5A1ft | Shortest length correct on the follow through |
| b1B1 | Cao (route) |
| b2B1ft | Their final value at B + their final value at K |
| c1M1 | Three distinct pairings of their four odd nodes |
| c1A1 | Any one row correct including pairing and total |
| c2A1 | Any two rows correct including pairing and total |
| c3A1 | All three rows correct including pairing and total |
| c4A1 | Cao – one combination of arcs that need traversing twice |
| c5A1 | Cao – both combination of arcs that need traversing twice |
| c6A1ft | \(196 +\) their smallest repeat out of a choice of at least two totals seen |
(a) | Network diagram shown with nodes and arcs labeled with times. Early event times shown in boxes. | M1 A1 (JEFD) A1 (BG) A1ft (HK) | (6) |
(b) | Quickest route: A – G – H – K. Shortest time: 32 (mins). Route from B to K via A: B – D – E – A – G – H – K. Length: 51 (mins) | A1 A1ft B1 B1ft | (6) |
(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$. Arcs AF, BK, KH or AE, ED, DB, FG, GH will be traversed twice. Route length = $196 + 34 = 230$ (mins) | M1 A1 A1 A1 A1 A1ft | (7) |
**Notes:**
| a1M1 | A larger value replaced by a smaller value at least once at B or H or K. |
| a1A1 | All values in J, F, E and D correct. |
| a2A1 | All values in B and G correct. |
| a3A1ft | All values in H and K correct on the follow through. |
| a4A1 | Cao (shortest path) |
| a5A1ft | Shortest length correct on the follow through |
| b1B1 | Cao (route) |
| b2B1ft | Their final value at B + their final value at K |
| c1M1 | Three distinct pairings of their four odd nodes |
| c1A1 | Any one row correct including pairing and total |
| c2A1 | Any two rows correct including pairing and total |
| c3A1 | All three rows correct including pairing and total |
| c4A1 | Cao – one combination of arcs that need traversing twice |
| c5A1 | Cao – both combination of arcs that need traversing twice |
| c6A1ft | $196 +$ their smallest repeat out of a choice of at least two totals seen |
**Total: 15 marks**
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-5_926_1479_219_296}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
[The total weight of the network is 196]\\
Figure 3 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.\\
(6)
On a particular day Oliver must travel from B to K via A.
\item Find a route of minimal time from B to K that includes A , and state its length.\\
(2)
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.
\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.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q4 [15]}}