Go backward to Solution to part (b)
Go up to 2 Searching on a simple graph
Solution to part (c)
You could have suggested dynamic programming, in that once the
distance tables have been computed they can be accessed quickly. The
problem is that you need a distance function to every possible
destination.
You could have suggested A* that will find shortest routes.
The problems is that the time and space is exponential in the path length.
The best solution is probably some hierarchical route finder, finding
distances between major intersections and then locally searching from a
particular location to these intersections.
Computational
Intelligence online
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999