Prev Up Next
Go backward to Solution to part (a)
Go up to 2 Searching on a simple graph
Go forward to Solution to part (c)

Solution to 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

Computational Intelligence online material, ©David Poole, Alan Mackworth and Randy Goebel, 1999

Prev Up Next