A2 June 2023 Q3
3.
Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J.
The number on each edge gives the length of the corresponding edge.
One application of Dijkstra’s algorithm has order \(n^2\), where \(n\) is the number of nodes in the network.
It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.
| Scheme | Marks | AO |
|---|---|---|
(i) | M1 A1 (ABCD) A1 (GEH) A1ft (FJ) | 1.1b 1.1b 1.1b 1.1b |
| Shortest path from A to J is ABCEHJ | A1 | 2.2a |
| Length of shortest path is 100 | A1ft | 2.2a |
| (6) |
Notes
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 D the working values must be 41 38 in that order (so 38 41 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, 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
M1: A larger value replaced by a smaller value in the working values at two of C or D or E or F or G or H or J
A1: All values in A, B, C and D correct. Condone lack of 0 in A’s working value
A1: All values G, E and H correct and the working values in the correct order. Penalise order of labelling only once per question (G, E and H must be labelled in that order and G must be labelled after A, B, C and D). Note that an additional working value of 80 at E after the 61 is not an error so 65 61 80 is fine, however, any other number or e.g. 80 65 61 in this order is incorrect and scores A0 in this part
A1ft: All values in F and J correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question.
To follow through F check that the working values at F follow from the candidate’s final values for the nodes that are directly attached to F (which are C, D, G and H). For example, if correct then the order of labelling of nodes C, D, G and H are 3, 4, 5 and 7 respectively so the working values at F should come from C, D, G and H in that order. The first working value at F should be their 31 (the Final value at C) + 43 (the weight of the arc CF), the second working value at F should be their 38 (the Final value at D) + 34 (the weight of the arc DF), the third working value at F should be their 59 (the Final value at G) + 11 (the weight of the arc GF), the fourth working value need not be there (as 68 + 22 > 70) but do not penalise if seen. Repeat the process for J (which will have working values from E and H with the order of these nodes determined by the candidate’s order of labelling at E and H)
A1: CAO - correct path from A to J (ABCEHJ) and not the path from J to A
A1ft: ft their final value at J only (if 100 stated and 100 is not the final value at J then A0)
| Scheme | Marks | AO |
|---|---|---|
| \(0.0312 \times \left(\dfrac{9000}{9}\right)^2\) | M1 | 1.1a |
| = 31 200 seconds therefore 520 minutes | A1 | 2.2a |
| (2) | ||
| (8 marks) |
Notes
M1: Complete, correct method – allow reciprocal e.g. \(0.0312 \times \left(\dfrac{9}{9000}\right)^2\) – allow slips in values only e.g. 0.312 for 0.0312. If using anything other than squared e.g. \(n^3\) then M0. The correct answer in seconds, minutes or hours (8 hours 40 minutes) implies this mark (and if in minutes implies the A mark too)
A1: CAO – the exact value of 520 must be stated at some point (as question specifically asked for the answer in minutes) – condone lack of units (but if present must be correct)