A* Search — Heuristic-Guided Shortest Path

Why it matters

Point-to-point pathfinding is orders of magnitude faster with A* than Dijkstra when a good heuristic exists. Any game, GPS, or robot needs this.

The architecture

Priority queue keyed by f(n) = g(n) + h(n): g is distance from start, h is heuristic estimate to goal. Expand node with smallest f. Same relaxation as Dijkstra but with better ordering.

Admissible heuristic: never overestimates true distance. Guarantees A* returns optimal path.

How it works end to end

Consistent heuristic (monotonic): h(n) ≤ cost(n, m) + h(m) for any edge. Stronger than admissible; enables closed-set optimizations.

Bidirectional A*: search from both start and goal, meet in middle. Even faster.

Weighted A*: multiply h by weight > 1. Trades optimality for speed. Useful when suboptimal-but-fast is enough.