Moderate -0.3 This is a standard Dijkstra's algorithm application with straightforward execution. Part (a) is routine algorithmic application, part (b) tests understanding of the method (simple explanation), and part (c) requires running Dijkstra twice but involves no conceptual challenge. Slightly easier than average due to being a direct textbook-style question with clear methodology.
[Network diagram with nodes and arc weights shown]
M1
A1 (ABCED)
A1 (GHFJ)
A1ft (KL)
Shortest route: \(A - B - C - E - D - K - L\)
A1
Length: 44 (km)
A1ft
(6)
Trace back from L including arc XY if (Y already lies on the path and) the difference between the final values of X and Y equals the weight of arc XY. OR e.g. \(44 - 10 = 34\) LK, \(34 - 10 = 24\) KD, \(24 - 5 = 19\) DE, \(19 - 5 = 14\) EC, \(14 - 4 = 10\) CB, \(10 - 10 = 0\) BA
B2, 1, 0
(2)
Shortest route: \(J - H - E - C - B - A - B - C - E - G - F\)
B1
Length: \(33 + 28 = 61\) (km)
B1ft
(2)
10 marks
Notes for Question 2:
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 35 34 33 in that order (so 35 33 34 is incorrect).
It is also important that the order of labelling is checked carefully – some candidates start with a label of 0 at A (rather than 1) – which is fine. Also the order of labelling must be a strictly increasing sequence – so 1, 2, 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 at least once in the working values at either D or E or F or 1 or L
- a1A1: All values in A, B, C, E and D correct and the working values in the correct order at E and D (including order of labelling). Condone lack of 0 in A's working value
- a2A1: All values G, H, F and J correct and the working values in the correct order. Penalise order of labelling only once per question (G, H, F and J must be labelled in that order and G must be labelled after A, B, C, E and D)
- a3A1ft: All values in K and L correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through K check that the working values at K follow from the candidate's final values from nodes D and J with the order of these values determined by the candidates order of labelling of D and J. Repeat this process for L (which will have working values from D and K with the order of these values determined by the candidates order of labelling of D and K). Note that an additional working value of 37 at K after the 34 is not an error so 34 37 is fine, however, any other number or 37 34 scores A0 in this part.
- a4A1: CAO - correct route (or from L to A)
- a5A1ft: Follow through on their final value at L only (condone lack of units)
- b1B1: General Explanation: Any indication of 'working backwards' or 'tracing back' through the network – it must be clear from the candidate's explanation that they are considering working backwards through the network but give food for seeing just the phrase 'working backwards' (oe). Calculation: Must see two consecutive correct calculations working backwards from L for their network – we do not need to see the corresponding nodes for this mark. Allow \(44 - 10 = 10 - 5 - 5 - 4 - 10 = 0\) for B1 only.
- b2B1: General explanation: For the second B mark we must see:
- Working backwards from L (not just 'end', 'or final node', etc.)
- Including an arc (XY) if the difference between the final values (of X and Y) is equal to the weight (of the arc XY)
- Must include all the words in bold (or their equivalent, for example, distance for weight, edge for arc,…) – technical language must be correct
Calculation: for the second B mark we must see all the correct calculations (so no follow through) from L to A for the correct diagram and the linking of all arcs/nodes to these calculations, for example, L: 44 – 10 = 34 K, etc. is acceptable. All values (including the 44 and 0) and nodes (including L and A) must be present. These marks in (b) are independent of the route stated in (a).
- c1B1: CAO (or from F to J)
- c2B1ft: 61 or their final value at J + their final value at F (condone lack of units) - dependent on first three B marks in (b) and the first mark in (c)
| Answer/Working | Marks | Guidance |
|---|---|---|
| [Network diagram with nodes and arc weights shown] | M1 | |
| | A1 (ABCED) | |
| | A1 (GHFJ) | |
| | A1ft (KL) | |
| **Shortest route**: $A - B - C - E - D - K - L$ | A1 | |
| **Length**: 44 (km) | A1ft | (6) |
| **Trace back from L** including arc XY if (Y already lies on the path and) the difference between the final values of X and Y equals the weight of arc XY. OR e.g. $44 - 10 = 34$ LK, $34 - 10 = 24$ KD, $24 - 5 = 19$ DE, $19 - 5 = 14$ EC, $14 - 4 = 10$ CB, $10 - 10 = 0$ BA | B2, 1, 0 | (2) |
| **Shortest route**: $J - H - E - C - B - A - B - C - E - G - F$ | B1 | |
| **Length**: $33 + 28 = 61$ (km) | B1ft | (2) |
| | **10 marks** | |
**Notes for Question 2:**
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 35 34 33 in that order (so 35 33 34 is incorrect).
It is also important that the order of labelling is checked carefully – some candidates start with a label of 0 at A (rather than 1) – which is fine. Also the order of labelling must be a strictly increasing sequence – so 1, 2, 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 at least once in the working values at either D or E or F or 1 or L
- **a1A1**: All values in A, B, C, E and D correct and the working values in the correct order at E and D (including order of labelling). Condone lack of 0 in A's working value
- **a2A1**: All values G, H, F and J correct and the working values in the correct order. Penalise order of labelling only once per question (G, H, F and J must be labelled in that order and G must be labelled after A, B, C, E and D)
- **a3A1ft**: All values in K and L correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through K check that the working values at K follow from the candidate's final values from nodes D and J with the order of these values determined by the candidates order of labelling of D and J. Repeat this process for L (which will have working values from D and K with the order of these values determined by the candidates order of labelling of D and K). Note that an additional working value of 37 at K after the 34 is not an error so 34 37 is fine, however, any other number or 37 34 scores A0 in this part.
- **a4A1**: CAO - correct route (or from L to A)
- **a5A1ft**: Follow through on their final value at L only (condone lack of units)
- **b1B1**: General Explanation: Any indication of 'working backwards' or 'tracing back' through the network – it must be clear from the candidate's explanation that they are considering working backwards through the network but give food for seeing just the phrase 'working backwards' (oe). Calculation: Must see two consecutive correct calculations working backwards from L for their network – we do not need to see the corresponding nodes for this mark. Allow $44 - 10 = 10 - 5 - 5 - 4 - 10 = 0$ for B1 only.
- **b2B1**: General explanation: For the second B mark we must see:
- Working backwards **from L** (not just 'end', 'or final node', etc.)
- Including an arc (XY) if the **difference between the final values** (of X and Y) is equal to the **weight** (of the arc XY)
- Must include all the words in bold (or their equivalent, for example, distance for weight, edge for arc,…) – technical language must be correct
Calculation: for the second B mark we must see all the correct calculations (so no follow through) from L to A for the correct diagram and the linking of **all** arcs/nodes to these calculations, for example, L: 44 – 10 = 34 K, etc. is acceptable. **All values (including the 44 and 0) and nodes (including L and A) must be present.** These marks in (b) are independent of the route stated in (a).
- **c1B1**: CAO (or from F to J)
- **c2B1ft**: 61 or their final value at J + their final value at F (condone lack of units) - dependent on first three B marks in (b) and the first mark in (c)
---
2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-03_848_1435_244_315}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents a network of roads. The number on each arc is the length, in km , of the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from A to L. State the shortest route and its length.
\item Explain how you determined the shortest route from your labelled diagram.
\item Find the length of the shortest route from J to F via A , and state your route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2019 Q2 [10]}}