Want to find path fromAto B - Dijk's gets you fromAto everywhere.
If graph doesn't change, Dijk's can be very useful, as you can precompute. However, if you have to
check on the fly, not as good, wasting time processing the same thing.
Looks in direction that is easy to travel, even if doesn't actually get any closer to the goal. If lots of easy
stuff in direction you don't want, end up wasting a lot of calculations/time. No measure of "how long
do I think this node will take me to get to the end?" - no end cost estimate.
No judgement if path is likely to be a good one.
A* helps address both these issues.
Doesn't do it with magic though. :(
Returns path from start vertex to target end vertex
Uses estimate of remaining cost to reach target and direct its search (how long will it take to reach end
vertex from current vertex)
Essentially the same implementation as Dijk's, but uses a different cost metric f
f has to components:
g: cost to reach current vertex from start (like Dijk's)
h: estimate of cost to reach goal vertex from current vertex (heuristic)
f = g + h
Key to efficiency is accuracy of h
To find optimal path h should be admissible:
Should not overestimate cost (underestimating is totally fine)
- if overestimate, may reach goal through another path, alg