A* Search

Imagine you're navigating with a GPS. Dijkstra's algorithm is like a GPS that has no idea where the destination is — it expands outward in all directions equally, like ripples in a pond, until it happens to reach your destination.

A* (A-star) is a GPS that knows roughly which direction the destination is. Instead of expanding in all directions, it biases the search toward the goal using an estimate called a heuristic. The result: it reaches the destination while exploring far fewer nodes.

The Evaluation Function: f(n) = g(n) + h(n)

Every node n gets a priority score:

• g(n) — the actual cost of the best known path from start to n so far
• h(n) — the heuristic estimate of cost from n to the goal
• f(n) = g(n) + h(n) — the estimated total cost of the cheapest path through n

The priority queue is ordered by f(n). Nodes with low estimated total cost are expanded first. This naturally steers the search toward the goal.

When h(n) = 0 for all n, f(n) = g(n), and A* reduces exactly to Dijkstra's algorithm. A* is a strict generalization.

Admissibility — The Key to Correctness

A heuristic h is admissible if it never overestimates the true cost: h(n) ≤ actual_cost(n, goal) for all n.

If h overestimates, A* may deprioritize the optimal path (thinking it's more expensive than it is) and settle on a suboptimal one. Admissibility guarantees the first time A* reaches the goal, it's via the optimal path.

Examples of admissible heuristics:

• Manhattan distance |Δx| + |Δy| — for 4-directional grid movement
• Euclidean distance √(Δ\(x^2\) + Δ\(y^2\)) — for free-direction movement

Consistency (Monotonicity) — Efficiency Guarantee

A stronger property: h is consistent if for every edge (n, n') with cost c, we have h(n) ≤ c + h(n'). This is the triangle inequality applied to the heuristic. Consistency implies admissibility, and additionally ensures that each node is processed only once — no re-expansions needed, just like Dijkstra.

Practical Impact

On a 1000×1000 grid, Dijkstra might explore 500,000 nodes before finding a path across. A* with Manhattan distance might explore only 5,000 — a 100× speedup. The better the heuristic (closer to the true cost without exceeding it), the fewer nodes A* explores.

When to Use A* vs. Dijkstra

Use A* when: you have a single target, and a meaningful heuristic is available. Use Dijkstra when: you need shortest paths to all destinations, or no good heuristic exists (h = 0 degenerates to Dijkstra anyway). A* is the standard algorithm in game pathfinding, GPS navigation, and robotics.