| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2020 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with unknown edge weight |
| Difficulty | Challenging +1.2 This question combines Dijkstra's algorithm with an algebraic parameter and then requires Chinese Postman reasoning. Part (a) is standard Dijkstra application but with symbolic algebra (requiring case analysis on x values). Part (b) requires understanding that the inspection route is a Chinese Postman problem, then using the given information to deduce x and find the shortest path. While multi-step, these are well-practiced D1 techniques applied systematically rather than requiring novel insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (a) [Network diagram with nodes and edges showing values at nodes] | M1 A1 A1 A1ft A1 (7) | In (a) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded e.g. at C the working values must be 22 21 20 in that order (22 20 21 is incorrect). It is also important that the order of labelling is checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, … will be penalised once (see notes below) but 1, 2, 3, 5, 6, … is fine. Errors in the final values and working values are penalised before errors in the order of labelling. a1M1: A larger value replaced by a smaller value in at least two of the working value boxes at any node except A, B, G or H (or once with at least two working values seen at H). a1A1: All values in A, B, D and C correct and the working values in the correct order at D and C (including order of labelling). a2A1: All values E and F correct and the working values in the correct order. Penalise order of labelling only once per question. a3A1ft: All values in G and H correct on the follow through and the working values in the correct order (the order at H must be correct but give bod). Penalise order of labelling only once per question. Ignore permanent label and final value at H only. Allow unsimplified expressions in \(x\) for the working values at H. a4A1: ABDH and 70; ABDEH and 37 + 2x; ABDEGH and 51 + x |
| If A0A0A0 for the final three marks in (a) then award A1A0A0 for all 3 routes stated correctly or all 3 correct values stated explicitly (so not just left in the working values at H). | ||
| (b) A to H are the only two odd nodes in the network so repeat arcs in a path from A to H. As a minimum: stating A and H as the odd nodes for the network (not just stating A and H) or stating a route from A to H with 5 nodes only or stating the need to repeat a path/route from A to H – this mark is for making their method clear | M1 | b1M1: Indication of repeating arcs in a path from A to H. As a minimum: stating A and H as the odd nodes for the network (not just stating A and H) or stating a route from A to H with 5 nodes only or stating the need to repeat a path/route from A to H – this mark is for making their method clear. |
| \(3x + 205 + 37 + 2x = 307\) | M1 | b2M1: \(3x + 205 +\) (one of their paths involving x) \(= 307\) – this mark is for making their method clear. |
| \(x = 13\) | A1 | b1A1: CAO (\(x = 13\)) – this mark is dependent on the second M mark only. |
| Time taken is 63 (minutes) | A1 (4) 11 marks | b2A1: CAO (63) – this mark is dependent on the second M mark only. |
| Answer | Marks | Guidance |
|--------|-------|----------|
| (a) [Network diagram with nodes and edges showing values at nodes] | M1 A1 A1 A1ft A1 (7) | **In (a) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded e.g. at C the working values must be 22 21 20 in that order (22 20 21 is incorrect).** It is also important that the order of labelling is checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, … will be penalised once (see notes below) but 1, 2, 3, 5, 6, … is fine. Errors in the final values and working values are penalised before errors in the order of labelling. a1M1: A larger value replaced by a smaller value in at least two of the working value boxes at any node except A, B, G or H (or once with at least two working values seen at H). a1A1: All values in A, B, D and C correct and the working values in the correct order at D and C (including order of labelling). a2A1: All values E and F correct and the working values in the correct order. Penalise order of labelling only once per question. a3A1ft: All values in G and H correct on the follow through and the working values in the correct order (the order at H must be correct but give bod). Penalise order of labelling only once per question. Ignore permanent label and final value at H only. Allow unsimplified expressions in $x$ for the working values at H. a4A1: ABDH and 70; ABDEH and 37 + 2x; ABDEGH and 51 + x |
| | If A0A0A0 for the final three marks in (a) then award A1A0A0 for all 3 routes stated correctly or all 3 correct values stated explicitly (so not just left in the working values at H). | |
| (b) A to H are the only two odd nodes in the network so repeat arcs in a path from A to H. As a minimum: stating A and H as the odd nodes for the network (not just stating A and H) or stating a route from A to H with 5 nodes only or stating the need to repeat a path/route from A to H – this mark is for making their method clear | M1 | b1M1: Indication of repeating arcs in a path from A to H. As a minimum: stating A and H as the odd nodes for the network (not just stating A and H) or stating a route from A to H with 5 nodes only or stating the need to repeat a path/route from A to H – this mark is for making their method clear. |
| | $3x + 205 + 37 + 2x = 307$ | M1 | b2M1: $3x + 205 +$ (one of their paths involving x) $= 307$ – this mark is for making their method clear. |
| | $x = 13$ | A1 | b1A1: CAO ($x = 13$) – this mark is dependent on the second M mark only. |
| | Time taken is 63 (minutes) | A1 (4) 11 marks | b2A1: CAO (63) – this mark is dependent on the second M mark only. |
---7.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{3aa30e8f-7d55-4c3b-8b2c-55c3e822c8a0-08_645_1474_221_285}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
[The total weight of the network is $205 + 3 x$ ]
Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road.
Malcolm wishes to minimise the time spent driving from his home at A to his office at H . The delays from roadworks on two of the roads leading in to H vary daily, and so the time taken to drive along these roads is expressed in terms of $x$, where $x$ is fixed for any given day and $x > 0$
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H. State the length of each route, leaving your answer in terms of $x$ where necessary.
On Monday, Malcolm needs to check each road. He must travel along each road at least once. He must start and finish at H and minimise the total time taken for his inspection route.
Malcolm finds that his minimum duration inspection route requires him to traverse exactly four roads twice and the total time it takes to complete his inspection route is 307 minutes.
\item Calculate the minimum time taken for Malcolm to travel from A to H on Monday. You must make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2020 Q7 [11]}}