A* search
Dijkstra with a sense of direction. To each place's cost it adds an estimate of the cost still to go, so it tries first the places that look closest to the goal.
- time O((V + E) log V)
- space O(V)
- priority queue
Priority queue: a waiting line where the cheapest one goes first, not the one that came first.
Other terms on this page
- Cost: what a move costs. On the maze, stepping onto ground costs 1, onto mud 3 and into water 9; on the graph, the number on the edge.
- Estimate (h): a guess of the cost still to go. A* stays exact only if the guess is never too high.
- Relaxing an edge: checking whether going through the current place gives a neighbour a cheaper cost, and taking it if it does.
Try this: Pick the open field and switch between Dijkstra and A*: both find a way of the same cost, but A* takes far fewer cells off the queue.
How it works
A* works like Dijkstra, but orders the queue by f = cost so far + h, where h estimates the cost still to go. On the maze h is the number of moves to M, ignoring walls and mud; on the graph it is the straight-line distance divided by 10. As long as h never guesses too high, the way A* has when it takes the goal is the cheapest one, exactly as with Dijkstra. The better the estimate, the fewer places it has to look at.
When it is a good choice
Use A* when you look for one goal and can estimate how far it is: pathfinding in games, robots, route planners on a map. With h = 0 it is exactly Dijkstra. An estimate that can guess too high makes A* faster but may cost you the cheapest way.