Graphs

A* Search

Dijkstra with a sense of direction: a heuristic pulls the search toward the goal, so it settles a fraction of the cells.

Same weighted terrain as Dijkstra. The blue settled region now stretches toward the target instead of spreading evenly; the green path is still optimal.

What you're seeing

This is Dijkstra's algorithm with one addition: a heuristic that estimates how far each cell still is from the target. The frontier is ordered not by cost-so-far alone, but by f = g + h — known cost plus estimated remaining cost. The effect is dramatic: instead of a roughly circular settled region, the blue blob elongates toward the target, ignoring cells that lead away from it. The readout shows the punchline — A* settles a small fraction of the cells Dijkstra needs, yet finds the very same optimal path.

The rule

a_star(source, target):
    g[source] = 0
    PQ keyed by f(n) = g[n] + h(n)        # h = estimated cost to target
    while PQ not empty:
        u = PQ.extract_min()              # smallest f
        if u == target: done
        for each neighbor v of u:
            if g[u] + weight(v) < g[v]:
                g[v] = g[u] + weight(v); parent[v] = u

With h ≡ 0 this is exactly Dijkstra. Here h is the Manhattan distance to the target times the cheapest possible terrain cost — a true lower bound on what's left to pay.

The invariant

The heuristic must be admissible: h(n) never over-estimates the true remaining cost to the target. Under that condition A* is optimal — the first time it extracts the target, g[target] is the true minimum cost. The reason: if the target were extracted with an inflated cost g* > optimal, then some node n on a genuine optimal path is still in the queue with f(n) = g(n) + h(n) ≤ g(n) + (\text{true remaining}) = \text{optimal} < g*, so n — not the target — would have been extracted first. Contradiction. The heuristic only reorders exploration toward the goal; because it can't overshoot, it can't make A* settle for a worse path. Push h beyond admissible (weighted A*) and you explore even less, but the optimality guarantee is gone.

The cost

Worst caseIn practice Cells settledO(V) (= Dijkstra)≪ V (goal-directed) TimeO((V+E) log V)

The asymptotic worst case is Dijkstra's — a useless (h = 0) or adversarial heuristic settles everything. The whole value is in the average case: a good heuristic shrinks the explored region toward a corridor between source and target, often by orders of magnitude. The better (closer to the true remaining cost) the heuristic, the fewer cells; a perfect heuristic would walk straight down the optimal path. The readout's "A* settled N vs Dijkstra M" is that saving, live.

In the wild

A* is the default for goal-directed pathfinding: game and robotics navigation (grid and navmesh), GPS routing (with landmark / ALT heuristics, and combined with contraction hierarchies for continental scale), puzzle solving (the 15-puzzle and Rubik's cube with pattern-database heuristics), and planning. It was born from the Shakey robot project at SRI (Hart, Nilsson & Raphael, 1968). The art is the heuristic: admissible keeps it optimal; the tighter it hugs the true cost, the faster it runs — which is why so much effort goes into designing good ones.

Try this

Open Dijkstra in another tab on the same idea and compare the settled regions: Dijkstra fills a fat blob in every direction; A* sends a narrow tongue straight at the target. Then raise Terrain roughness — expensive terrain forces both to detour, and you can watch A* still commit toward the goal while respecting the cost.

References

  1. Hart, P. E., Nilsson, N. J. & Raphael, B. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Trans. Systems Science and Cybernetics 4(2):100–107, 1968. The original A*.
  2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS) — shortest paths and admissible heuristics. MIT Press, 2022.
  3. Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach, Ch. 3 (Informed Search) — admissibility, consistency, optimality.