A* Search

A* (“A-star”) is Dijkstra with a sense of direction. Dijkstra explores blindly outward in all directions; A* uses an estimate of “how far is this node from the goal?” to explore preferentially toward the target. When the estimate is good, it examines a tiny fraction of the nodes Dijkstra would — which is why it’s the default pathfinder in games and on grids.

The key idea: f = g + h

Dijkstra always expands the node with the smallest distance-so-far. A* expands the node with the smallest estimated total path cost:

$$f(n) = g(n) + h(n)$$

• $g(n)$ — the actual cost from the start to $n$ (exactly Dijkstra’s distance).
• $h(n)$ — the heuristic: an estimate of the remaining cost from $n$ to the goal.
• $f(n)$ — the estimated cost of the best path through $n$.

By ordering the priority queue on $f$ instead of $g$, A* prefers nodes that look like they’re on a good path to the goal, instead of just nodes that are close to the start.

The algorithm

It’s Dijkstra with two changes: the queue is keyed on $f = g + h$, and we add $h$ when computing priorities.

A*(graph, start, goal, h):
    g[start] ← 0
    g[v] ← ∞ for every other v
    parent[v] ← none
    open ← min-priority-queue keyed on f, holding (h(start), start)

    while open is not empty:
        u ← open.pop_min()             # smallest f = g + h
        if u == goal:
            return reconstruct(parent, goal)
        for each edge (u → v) with weight w:
            tentative ← g[u] + w
            if tentative < g[v]:       # ---- relaxation, on g only ----
                g[v] ← tentative
                parent[v] ← u
                f ← g[v] + h(v)
                open.push((f, v))
    return "no path"

Notice the relaxation still works on the true cost $g$ — the heuristic only influences the order of exploration, never the recorded distances. That separation is what keeps the answer correct.

The heuristic makes or breaks it

Everything hinges on $h$. Two properties matter:

• Admissible — $h(n)$ never overestimates the true remaining cost. This guarantees A* returns an optimal (genuinely shortest) path.
• Consistent (monotone) — for every edge $u \to v$ of weight $w$, $h(u) \le w + h(v)$. Consistency implies admissibility and additionally means each node is finalized only once (no re-expansions), exactly like Dijkstra.

Common admissible heuristics on a grid:

Movement allowed	Use this $h$	Why admissible
4 directions (no diagonals)	Manhattan $\lvert\Delta x\rvert + \lvert\Delta y\rvert$	You can’t beat the axis-aligned step count
8 directions (diagonals)	Chebyshev $\max(\lvert\Delta x\rvert, \lvert\Delta y\rvert)$	Diagonal moves cover both axes at once
Any-angle / geographic	Euclidean $\sqrt{\Delta x^2 + \Delta y^2}$	Straight line is the true lower bound

The two extremes are illuminating:

• $h(n) = 0$ everywhere → A* becomes Dijkstra (no guidance, still correct).
• $h(n) =$ the exact remaining cost → A* walks straight to the goal, expanding only nodes on the optimal path.

Real heuristics live between these. The closer $h$ hugs the true cost (while staying admissible), the less A* explores. An inadmissible $h$ that overestimates can make A* faster still — but it may return a suboptimal path, a trade sometimes worth making (“weighted A*”).

Complexity

Worst case is the same as Dijkstra, $O((V+E)\log V)$ — a useless heuristic ($h=0$) degrades exactly to it. But with a good heuristic the effective branching factor drops sharply, and in practice A* explores dramatically fewer nodes. Its cost is problem-dependent: it’s about how well $h$ approximates reality, not a clean formula.

When to use it

• Grids and games — pathfinding on tile maps is the canonical use; Manhattan or Chebyshev distance is right there for free.
• Geographic routing — straight-line (great-circle) distance is a natural admissible heuristic for road networks.
• Any search with a good lower-bound estimate — puzzles (15-puzzle, Rubik’s cube) where you can cheaply estimate distance-to-solved.
• Skip it when you have no meaningful heuristic — then it’s just Dijkstra with extra bookkeeping, and bidirectional Dijkstra is the better speedup. (Bidirectional A* exists too, but combining the stopping rule with heuristics correctly is notoriously fiddly.)