D1 June 2011 Q6
6.
Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.
(a) Use Dijkstra’s algorithm to find the shortest route from A to H. State your shortest route and its length. (6)
(b) Explain how you determined your shortest route from your labelled diagram. (2)
The track between E and F is now closed for resurfacing and cannot be used.
(c) Find the shortest route from A to H and state its length. (2)
| Scheme | Marks |
|---|---|
 | M1 A1 (ABCD) A1ft (EF) A1ft (GH) |
| ACDFEGH | A1 |
| Length 71 (km) | A1ft |
| (6) |
Notes
(a)M1 Big replaced by smaller at least once at B or D or E or G or H
1A1 A, B, C, D boxes all correct, condone lack of 0 in ‘s working value
2A1ft E and F ft correctly
3A1ft G and H ft correctly
4A1 CAO
5A1ft ft on their final value.
| Scheme | Marks |
|---|---|
| E.g. 71 – 12 = 59 GH 49 – 10 = 39 FE 24 – 13 = 11 CD 59 – 10 = 49 EG 39 – 15 = 24 DF 11 – 11 = 0 AC Or Trace back from H including arc XY if (Y already lies on the path and) the difference of the final values of X and Y equals weight of arc XY. | B2,1,0 |
| (2) |
Notes
(b)1B1 Attempting an explanation, at least 3 stages or one half of general explanation
2B1 Correct explanation – all six stages, both halves of explanation
| Scheme | Marks |
|---|---|
| ACBEGH | B1 |
| Length 72 (km) | B1 |
| (2) | |
| (10 marks) |
Notes
(c)1B1 CAO
2B1 CAO