Standard +0.8 This is a substantial multi-part question combining Dijkstra's algorithm with route inspection (Chinese Postman Problem). While individual components are standard D1 techniques, part (c) requires careful identification of odd vertices after removing edges, and part (e) requires understanding that an Eulerian path connects two odd vertices. The question demands sustained accuracy across multiple algorithms and careful bookkeeping, placing it moderately above average difficulty.
\end{figure}
\section*{[The total weight of the network is 223]}
Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.
Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length.
On a particular day, Pamela must include C in her route.
Find the shortest route from A to B that includes C , and state its length.
(2)
Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
Write down a possible route, and calculate its length. You must make your calculation clear.
Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).
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 H the working values must be 30 27 24 in that order (30 24 27 is incorrect) and with no additional working values. It is also important that the order of labelling checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, 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 at least once in the working values at either B or C or E or F or H
a1A1: All values at A, D, G, F correct and the working values in the correct order at F. Condone lack of 0 in A's working value – please check carefully for a 9 in the working values at D
a2A1: All values at H and C correct and the working values in the correct order. Penalise order of labelling only once per question (H and C must be labelled in that order and H labelled after A, C and D)
a3A1: All values in E and B correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question (E and B must be labelled in that order and E labelled after all other nodes (excluding B)). To follow through E check that all working values at E follow from the candidate's final values from nodes D and H (in the order that the candidate has labelled these two nodes) and that the final value, and order of labelling, follows through correctly. Repeat this process for B (which will have working values from D, E and H))
a4A1: CAO - ADGFHEB
b1B1: CAO - ADGFCFHEB
b2B1ft: Ft their final value at B
c1M1: Three distinct pairings of B, E, G and H
c1A1: Any two rows correct including pairings and totals
c2A1: All three rows correct including pairings and totals
c3A1: CAO correct arcs clearly (not just in their working) stated: BE, FG and FH. Do not accept GH, GFH or GH via F
d1B1: Any correct route (the route may be given in terms of either vertices (ADF...) or arcs (AD, DF, FG,...)) – checks: start and finish at A, 17 vertices (repeats BE, FG, FH and nodes A(2), B(2), D(3), E(2) F(3), G(2), H(3))
d1M1: complete method: 223 + (their smallest repeat out of a choice of at least two totals seen) – (at least two arcs incident to C) or the correct answer of 190
d1A1: CAO with full working – accept as a minimum 223 + 16 – 49 but not just 190 or 223 - 33
e1B1: CAO (G)
e2B1: CAO (10)
| Answer/Scheme | Marks | Guidance |
|---|---|---|
| (a) | M1 A1 (ADGF) A1 (HC) A1ft (EB) | (4) |
| (b) Shortest Path: ADGFHEB; Length: 36 (km); Route: ADGFCFHEB; Length: 25 + 21 = 46 (km) | A1 A1ft B1 B1ft | (6) |
| (c) $G(F)H + EB = 10 + 6 = 16*$; $G(FH)E + H(E)B = 16 + 12 = 28$; $G(FHE)B + HE = 22 + 6 = 28$; Repeat BE, FG & FH | M1 A1 A1 A1 | (4) |
| (d) Route: e.g. ADFGDHGFHEDBEBHFA; Length: 223 + 16 – 27 – 17 – 5 = 190 (km) | B1 M1 A1 | (3) |
| (e) Finishing point: G; Difference is 16 – 6 = 10 (km) | B1 B1 | (2) |
| | **17 marks** | |
**Notes for Question 6:**
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 H the working values must be 30 27 24 in that order (30 24 27 is incorrect) and with no additional working values. It is also important that the order of labelling checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, 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 at least once in the working values at either B or C or E or F or H
a1A1: All values at A, D, G, F correct and the working values in the correct order at F. Condone lack of 0 in A's working value – please check carefully for a 9 in the working values at D
a2A1: All values at H and C correct and the working values in the correct order. Penalise order of labelling only once per question (H and C must be labelled in that order and H labelled after A, C and D)
a3A1: All values in E and B correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question (E and B must be labelled in that order and E labelled after all other nodes (excluding B)). To follow through E check that all working values at E follow from the candidate's final values from nodes D and H (in the order that the candidate has labelled these two nodes) and that the final value, and order of labelling, follows through correctly. Repeat this process for B (which will have working values from D, E and H))
a4A1: CAO - ADGFHEB
b1B1: CAO - ADGFCFHEB
b2B1ft: Ft their final value at B
c1M1: Three distinct pairings of B, E, G and H
c1A1: Any two rows correct including pairings and totals
c2A1: All three rows correct including pairings and totals
c3A1: CAO correct arcs clearly (not just in their working) stated: BE, FG and FH. Do not accept GH, GFH or GH via F
d1B1: Any correct route (the route may be given in terms of either vertices (ADF...) or arcs (AD, DF, FG,...)) – checks: start and finish at A, 17 vertices (repeats BE, FG, FH and nodes A(2), B(2), D(3), E(2) F(3), G(2), H(3))
d1M1: complete method: 223 + (their smallest repeat out of a choice of at least two totals seen) – (at least two arcs incident to C) or the correct answer of 190
d1A1: CAO with full working – accept as a minimum 223 + 16 – 49 but not just 190 or 223 - 33
e1B1: CAO (G)
e2B1: CAO (10)
---
6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-08_1031_1502_242_333}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
\section*{[The total weight of the network is 223]}
Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length.
On a particular day, Pamela must include C in her route.
\item Find the shortest route from A to B that includes C , and state its length.\\
(2)
Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
\item Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
\item Write down a possible route, and calculate its length. You must make your calculation clear.
Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
\item State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2017 Q6 [17]}}