Go backward to Solution to Question 2, part 4
Go up to Question 2
Solution to Question 2, part 5
If the graph had extended infinitely in all directions, A*
would still find a solution. Depth-first search would wander off
infinitely. Dynamic programming would find a path from s to g, but
then continue off forever. If you stopped it when it had included s
in the distance map, it would find the shortest path, but this
would be the same as a shortest-first search from g, which still
isn't as good as A*. It would let us reuse the distance
function build for other starting positions.