D1 June 2013 (R) Q7
7.
Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either C1 or C2. A route of minimum length is required.
It is decided to use Dijkstra’s algorithm to find the shortest routes between C1 and J and between C2 and J.
| Scheme | Marks |
|---|---|
| E.g. We would be able to find the shortest distance from J to every other vertex. E.g. We would only need to apply Dijkstra’s algorithm once. | B1 |
| (1) |
Notes
a1B1 CAO
| Scheme | Marks |
|---|---|
 | M1 A1 (G, H, I J) A1(D, E, F) A1ft (C1, C2) |
| Shortest route is C2EFGIJ length 48 (miles) | A1 A1ft |
| (6) | |
| (7 marks) |
Notes
b1M1 A larger value replaced by a smaller value at least once in the working values at either G, E, D, C1 or C2.
b1A1 All values in G, H, I and J correct. The working values at G must be in the correct order. Condone lack of 0 in the working value at J.
b2A1 All values in D, E and F correct and the working values in the correct order. Penalise order of labelling only once per question. (F, E and D labelled in that order with G, H, I and J labelled before F).
b3A1ft All values in C1 and C2 ft correct and the working values in the correct order. Penalise order of labelling only once per question. (C2 labelled after all other nodes (D to J) – condone lack of final value or order of labelling for C1)
b4A1 Route CAO
b5A1ft Their final value ft (if answer is not 48 ft their final value at either C1 or C2 dependent on their route)
If the candidate uses either C1 or C2 as the starting vertex then this is not a misread. They can score a maximum of M1A0A0A0A1A1ft. If starting at:
C1 – M1 for a larger value replaced by a smaller value at either C2, F, G, H, I or J , then A0 A0 A0 then A1 for the route (C1DFGIJ) and then A1 for 49 (or ft their final value at J).
C2 – M1 for a larger value replaced by a smaller value at either C1, F, G, H, I or J, then A0 A0 A0 then A1 for the route (C2 EFGIJ) and then A1 for 48 (or ft their final value at J).
If the candidate uses both C1 and C2 as the starting vertices then award M1 for a larger value replaced by a smaller value at either F, G, H, I or J, then A0 A0 A0 then A1 for the correct route only (C2 EFGIJ) and A1 for 48 (no ft).