AlgoScope

A* Search

Best-first search ordered by g + h, distance so far plus an admissible estimate of what is left. Optimal and far more focused than BFS.

Shortest path, algorithm, advanced
Expand (0,0), 2 new cells.01234501234011
Expand (0,0), 2 new cells.01234501234011

Grid Search and A*: A* leans toward the goal

Decision, step 2 of 23

Expand (0,0), g = 0, f = 9. New neighbours (1,0), (0,1) get g = 1 and f = 9, 9. Frontier: 2.

How grid search and a* works

Cost

Best
O(E)
Average
depends on heuristic
Worst
O(E log V)
Space
O(V)

Worst case equals Dijkstra with a zero heuristic.