A2 October 2021 Q6
6.
In Figure 4 the weights on the arcs represent distances.
One application of Dijkstra’s algorithm has order \(n^2\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra’s algorithm from each node of the network.
It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
| Scheme | Marks | AO |
|---|---|---|
(i) | M1 A1 A1 A1ft | 1.1b 1.1b 1.1b 1.1b |
| Shortest path from A to H: ABEFGH | A1 | 2.2a |
| (ii) Length of shortest path from A to H is 112 | 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 H the working values must be 129 118 112 in that order (so 129 112 118 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
(a) M1: A larger value replaced by a smaller value in at least two of the working boxes at either D or F or G or H
A1: All values in A, B, C and E correct. Condone lack of 0 in A’s working value
A1: All values D and F correct and the working values in the correct order. Penalise order of labelling only once per question (D and F must be labelled in that order and D must be labelled after A, B, C and E)
A1ft: All values in G and H correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through G check that the working value at G follows from the candidate’s final values from their feeds into G (which will most likely come from nodes C, D and/or F (in the order in which the candidate has labelled them)) and that the final value, and order of labelling, follows through correctly. Repeat this process for H (which will possibly have working values from C, F and/or G with the order of these values determined by the candidate’s order of labelling at C, F and G)
A1: cao - correct path from A to H (ABEFGH)
A1ft: Follow through their final value at H only (if 112 stated and 112 is not the final value at H then A0)
| Scheme | Marks | AO |
|---|---|---|
| Applying Dijkstra repeatedly to \(n\) nodes implies that the order is \(n(n^2) = n^3\) | B1 | 3.1b |
| \(t = 0.082\left(\dfrac{200}{10}\right)^3\) | M1 | 3.4 |
| = 656 (seconds) | A1 | 2.2a |
| (3) |
Notes
(b) B1: Any indication that repeated application of Dijkstra has cubic order
M1: Complete method – allow 10/200 – allow slips in values e.g. 0.82 for 0.082 and accept 200/10 (or 10/200) either squared or cubed only
A1: cao
| Scheme | Marks | AO |
|---|---|---|
| e.g. order of \(n^3\) does not mean that the order is proportional to \(n^3\) (which is the assumption behind the answer in (b)) but merely means that the dominant term is of order \(n^3\) | B1 | 3.2b |
| (1) | ||
| (10 marks) |
Notes
(c) B1: Any indication that the run-time is not exactly proportional to \(n^3\) e.g., may suggest that there are other terms (\(n^3 + \ldots\)), or that \(n^3\) is the dominant term, or that order does not imply proportionality. Do not accept only that ‘\(n^3\) is not exact’. Condone use of \(n^2\) (oe) for \(n^3\)