Prev Up
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

Prev Up