D1 June 2005 Q6
6.
Figure 5 shows a network of roads. The number on each arc represents the length of that road in km.
(a) Use Dijkstra’s algorithm to find the shortest route from \(A\) to \(J\). State your shortest route and its length. (5)
(b) Explain how you determined the shortest route from your labelled diagram. (2)
The road from \(C\) to \(F\) will be closed next week for repairs.
(c) Find the shortest route from \(A\) to \(J\) that does not include \(CF\) and state its length. (3)
| Scheme | Marks |
|---|---|
 | M1 A1 A1ft A1ft |
| Route: \(ACFEGJ\) length: 53 km | A1 |
| (5) |
| Scheme | Marks |
|---|---|
| General explanation – trace back from \(J\) – include arc \(XY\) if \(Y\) is already on path and if difference in final labels equals length of arc. Specific explanation – \(53 - 15 = 38\ \ GJ\) \(38 - 6 = 32\ \ EG\) \(32 - 4 = 28\ \ FE\) \(28 - 10 = 18\ \ CF\) \(18 - 18 = 0\ \ AC\) | B2ft,1ft,0 |
| (2) |
| Scheme | Marks |
|---|---|
| e.g. \(ADFEGJ\) or \(ACEGJ\); length 54 km | M1 A1; A1 |
| (3) | |
| (10 marks) |