A* Pathfinding
Dijkstra plus a compass: rank the frontier by g (cost so far) + h (estimated cost to goal). With an admissible heuristic it finds optimal paths while expanding far fewer nodes.
- Category
- Graphs
- Time complexity
- O(E log V)
- Space complexity
- O(V)
Pseudocode
open ← {start}
expand lowest f = g + h
update neighbours, close node
stop when goal expanded
Reference implementation
f(n) = g(n) + h(n)
# g — steps from start
# h — Manhattan distance to goal
expand lowest-f node first
# h admissible → optimal path