Moderate -0.3 This is a standard D1 Dijkstra question with routine extensions. Part (b) is textbook application of the algorithm, part (c) simply requires combining two shortest paths, and parts (d)-(e) are standard Chinese Postman algorithm application. All techniques are algorithmic procedures requiring minimal problem-solving insight, making this slightly easier than average A-level maths.
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-06_899_1241_230_411}
\captionsetup{labelformat=empty}
\caption{Figure 4 [0pt]
[The total weight of the network is 88]}
\end{figure}
Explain what is meant by the term 'path'.
(2)
Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.
(6)
On a particular day, Tomek needs to travel from G to J via A.
Find the shortest route from G to J via A , and find its length.
(3)
The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
Use an appropriate algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
(5)
Write down a possible shortest inspection route.
(1)
A path is a (i) (finite) sequence of edges, such that (ii) the end vertex of one edge in the sequence is the start vertex of the next, and in which (iii) no vertex appears more than once
B2, 1, 0
(2)
Shortest path: \(A – B – C – F – E – J\)
M1, A1 (BCF)
(6)
Shortest length: \(16\) (km)
A1ft
Shortest path from A to G: \(A – B – C – F – H – G\)
B1
(3)
Shortest route from G to J via A: \(G – H – F – C – B – A – B – C – F – E – J\)
B1
Length: \(16 + 12 = 28\) (km)
B1ft
\(A(BCFE)D + EF = 13 + 3 = 16\); \(A(BCFE)D(E)F = 11 + 5 = 16\); \(A(BCF + DE = 8 + 2 = 10^*\); Arcs AB, BC, CF, DE will be traversed twice; Route length \(= 88 - 7 + 10 = 91\) (km)
M1, A1ft, A1ft, A1, A1
(5)
Route e.g. BABCBGHFJBEDACFDEFCB
B1
(1)
17 marks
Notes for Question 5:
- a1B1: One of the three points made clearly or two suggested. Arcs(edges)/vertices(nodes) must be referred to correctly. Do not condone incorrect technical language e.g. point for vertex
- a2B1: All three points made clearly
- 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 J the working values must be 20 17 16 in that order (20 16 17 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
- b1M1: A larger value replaced by a smaller value at least once at C or D or F or G or J
- b1A1: All values in B, C and F correct and the working values in the correct order
- b2A1: All values in H, E and G correct and the working values in the correct order. Penalise order of labelling only once per question (H, E and G must be labelled in that order and H must be labelled after A, B, C and F)
- b3A1ft: All values in D and J correct on the flow through and the working values in the correct order. To follow through D check that all the working values at D follow from the candidate's final values from nodes A, C and E (in the order that the candidate has labelled these three nodes) and that the final value, and order of labelling, follows through correctly. Repeat this process for J (which will have working values from F, H and E)
- b4A1: CAO for the path (from either A to J or J to A)
- b5A1ft: If their answer is not 16 follow through their final value at J (condone lack of units)
- c1B1: Shortest path from A to G stated correctly (most probably stated implicitly as part of their shortest route from G to J via A)
- c2B1: Shortest path from G to J via A stated correctly
- c3B1ft: Shortest route length correct on the follow through (their final value at G + their final value at J)
- d1M1: Three distinct pairings of the correct four odd nodes
- d1A1ft: Any two rows correct including pairing and totals (the ft on this and the next A mark in (d) is for using their final values at D, E and F from (b) for the lengths of AD, AE and AF only)
- d2A1ft: All three rows correct including pairing and total (using their final values at D, E and F from (b))
- d3A1: CAO correct arcs clearly stated (no ft on this mark)
- d4A1: CAO (no ft on this mark)
- e1B1: Any correct route – checks: starts and finishes at B, 19 vertices, AB, BC, CF, DE repeated and A appears 2, B(4), C(3), D(2), E(2), F(3), G(1), H(1), J(1)
| Answer/Working | Marks | Guidance |
|---|---|---|
| A path is a (i) (finite) sequence of edges, such that (ii) the end vertex of one edge in the sequence is the start vertex of the next, and in which (iii) no vertex appears more than once | B2, 1, 0 | (2) |
| **Shortest path:** $A – B – C – F – E – J$ | M1, A1 (BCF) | (6) |
| **Shortest length:** $16$ (km) | A1ft | |
| **Shortest path from A to G:** $A – B – C – F – H – G$ | B1 | (3) |
| **Shortest route from G to J via A:** $G – H – F – C – B – A – B – C – F – E – J$ | B1 | |
| **Length:** $16 + 12 = 28$ (km) | B1ft | |
| $A(BCFE)D + EF = 13 + 3 = 16$; $A(BCFE)D(E)F = 11 + 5 = 16$; $A(BCF + DE = 8 + 2 = 10^*$; Arcs AB, BC, CF, DE will be traversed twice; Route length $= 88 - 7 + 10 = 91$ (km) | M1, A1ft, A1ft, A1, A1 | (5) |
| Route e.g. BABCBGHFJBEDACFDEFCB | B1 | (1) |
| | | **17 marks** |
**Notes for Question 5:**
- a1B1: One of the three points made clearly or two suggested. Arcs(edges)/vertices(nodes) must be referred to correctly. Do not condone incorrect technical language e.g. point for vertex
- a2B1: All three points made clearly
- **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 J the working values must be 20 17 16 in that order (20 16 17 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**
- b1M1: A larger value replaced by a smaller value at least once at C or D or F or G or J
- b1A1: All values in B, C and F correct and the working values in the correct order
- b2A1: All values in H, E and G correct and the working values in the correct order. Penalise order of labelling only once per question (H, E and G must be labelled in that order and H must be labelled after A, B, C and F)
- b3A1ft: All values in D and J correct on the flow through and the working values in the correct order. To follow through D check that all the working values at D follow from the candidate's final values from nodes A, C and E (in the order that the candidate has labelled these three nodes) and that the final value, and order of labelling, follows through correctly. Repeat this process for J (which will have working values from F, H and E)
- b4A1: CAO for the path (from either A to J or J to A)
- b5A1ft: If their answer is not 16 follow through their final value at J (condone lack of units)
- c1B1: Shortest path from A to G stated correctly (most probably stated implicitly as part of their shortest route from G to J via A)
- c2B1: Shortest path from G to J via A stated correctly
- c3B1ft: Shortest route length correct on the follow through (their final value at G + their final value at J)
- d1M1: Three distinct pairings of the correct four odd nodes
- d1A1ft: Any two rows correct including pairing **and** totals (the ft on this and the next A mark in (d) is for using their final values at D, E and F from (b) for the lengths of AD, AE and AF only)
- d2A1ft: All three rows correct including pairing and total (using their final values at D, E and F from (b))
- d3A1: CAO correct arcs clearly stated (no ft on this mark)
- d4A1: CAO (no ft on this mark)
- e1B1: Any correct route – checks: starts and finishes at B, 19 vertices, AB, BC, CF, DE repeated and A appears 2, B(4), C(3), D(2), E(2), F(3), G(1), H(1), J(1)
---
5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-06_899_1241_230_411}
\captionsetup{labelformat=empty}
\caption{Figure 4\\[0pt]
[The total weight of the network is 88]}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Explain what is meant by the term 'path'.\\
(2)
Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
\item Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.\\
(6)
On a particular day, Tomek needs to travel from G to J via A.
\item Find the shortest route from G to J via A , and find its length.\\
(3)
The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
\item Use an appropriate algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.\\
(5)
\item Write down a possible shortest inspection route.\\
(1)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q5 [17]}}