D1 June 2009 Q6
6.
Figure 4 represents a network of roads. The number on each arc gives the length, in km, of that road.
(a) Use Dijkstra’s algorithm to find the shortest distance from A to I. State your shortest route. (6)
(b) State the shortest distance from A to G. (1)
| Scheme | Marks |
|---|---|
 | M1 1A1 2A1ft 3A1ft 4A1ft |
| Route: A E H I | 5A1 |
| (6) |
Notes
(a) 1M1: Small replacing big in the working values at C or F or G or I
1A1: Everything correct in boxes at A, B, D and F
2A1ft: ft boxes at E and C handled correctly but penalise order of labelling only once
3A1ft: ft boxes at G and H handled correctly but penalise order of labelling only once
4A1ft: ft boxes at I handled correctly but penalise order of labelling only once
5A1: route cao A E H I
| Scheme | Marks |
|---|---|
| Shortest distance from A to G is 28 km | B1ft |
| (1) | |
| (7 marks) |
Notes
(b) 1B1ft: ft their final label at G condone lack of km