Go backward to Solution to Question 2, part (a)
Go up to Question 2 [15 marks]
Go forward to Solution to Question 2, part (c)
Solution to Question 2, part (b)
Dynamic programming builds the following distance map to sp
|
Node | Distance |
|
SP | 0 |
|
DT | 2 |
|
KB | 4 |
|
JB | 8 |
|
MP | 8 |
|
BBY | 10 |
|
UBC | 11 |
|
KD | 11 |
|
RM | 11 |
|
AP | 14 |
|
SRY | 32
|
To get from UBC to SP,
you need to compare going via JB (with distance 3+8) with going via KD
(distance 3+11). Thus the first step is to JB. From JB, you need to
compare going via KB (distance 8), via KD (distance 15) and UBC
(distance 14) and choose KB. From KB, you choose DT and then SP. The
final route is:
UBC -> JB -> KB -> DT -> SP