A* Search: The Heuristic Shortest-Path Algorithm Powering GPS and Game AI

The core idea: guide the search with a lower bound

Dijkstra's algorithm explores nodes in increasing order of g(n), the known cost from the start. It has no idea where the goal is, so it grows a uniform-cost ball outward. A* fixes this by adding a heuristic h(n) — a cheap estimate of the remaining cost from n to the goal — and ordering the frontier by the sum:

f(n) = g(n) + h(n)
       └──┬──┘   └──┬──┘
   cost so far   estimated cost to go

f(n) is an estimate of the total cost of the cheapest path from start to goal that passes through n. Because A* always expands the frontier node with the smallest f, it prioritizes nodes that look like they lie on a good path toward the goal. Two special cases bracket it: set h ≡ 0 and A* degenerates exactly into Dijkstra; ignore g and order by h alone and you get greedy best-first search, which is fast but not optimal. A* is the principled interpolation between them.

The critical property of h is admissibility: h(n) ≤ h*(n) for every node, where h*(n) is the true optimal cost-to-go. An admissible heuristic never overestimates — it is an optimistic lower bound. On a map, straight-line (Euclidean) distance is admissible because no road can be shorter than the crow-flies line; for grid movement, Manhattan or Chebyshev distance serve the same role.

The algorithm, step by step

A* maintains two structures: an open set (a priority queue keyed on f, usually a binary min-heap) and a closed set of already-expanded nodes. A came_from map records each node's best parent so the path can be reconstructed at the end.

function AStar(start, goal, h):
  open   = PriorityQueue()          # keyed by f = g + h
  g      = { start: 0 }             # best known cost from start
  came_from = {}
  open.push(start, h(start))
  while open not empty:
    n = open.pop_min()              # smallest f
    if n == goal: return reconstruct(came_from, n)
    for (m, w) in neighbors(n):     # edge n→m of weight w
      tentative = g[n] + w
      if tentative < g.get(m, +inf):
        came_from[m] = n
        g[m] = tentative
        open.push(m, tentative + h(m))   # decrease-key or lazy re-insert
  return FAILURE                    # goal unreachable

The loop invariant is the heart of the proof: when A* pops a node n and h is consistent, g[n] already equals the true shortest distance to n. Consistency means h(n) ≤ w(n, m) + h(m) for every edge — the triangle inequality on the heuristic. Under consistency, f is non-decreasing along any path A* expands, so once a node is closed it is never improved and can be safely skipped. The moment goal is popped, its f equals its g (since h(goal) = 0) and that value is optimal.

• Relaxation: the tentative < g[m] check is the same edge relaxation Dijkstra uses; A* just biases the queue order.
• Lazy deletion: most implementations skip decrease-key and instead push a duplicate entry, discarding stale pops when n is already closed. Simpler, and often faster than a Fibonacci heap in practice.
• Tie-breaking: among equal f, preferring larger g (closer to goal) reduces expansions noticeably.

Why it's optimal — and optimally efficient

A* enjoys two theorems from the original 1968 paper. Optimality (admissible h): A* returns a least-cost path. Suppose it returned a suboptimal path to the goal with cost C > C*. Before the goal was popped, some node n on the true optimal path was still on the open set. For that node, f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C* (using admissibility). But f(goal) = C > C* ≥ f(n), so A* would have popped n before the suboptimal goal — a contradiction.

Optimal efficiency (consistent h): among all algorithms that use the same heuristic and are guaranteed to find optimal paths, A* expands the fewest nodes (up to tie-breaking). Every node it expands has f(n) ≤ C*, and any optimal algorithm must expand those nodes — else it could miss a cheaper path hidden behind one. This is why you cannot beat A* without either a better heuristic or giving up on optimality.

The quality of h is captured by informedness: if h₁(n) ≥ h₂(n) everywhere (both admissible), then h₁ dominates h₂ and A* with h₁ never expands more nodes than with h₂. The perfect heuristic h = h* makes A* walk straight down the optimal path, expanding only O(d) nodes; the useless h = 0 makes it Dijkstra. Real heuristics live between, and closing that gap is where all the engineering effort goes.

Complexity: the honest bounds

The theoretical worst case is grim. On an implicit search tree with branching factor b and optimal solution depth d, A* can expand O(b^d) nodes in both time and space, exactly like breadth-first search, whenever the heuristic gives no useful discrimination (e.g. h ≡ 0 with unit costs). More precisely, the number of expansions is exponential in the heuristic error: A* runs in polynomial time only if |h(n) − h*(n)| = O(log h*(n)). Most practical heuristics have constant relative error, so the count stays exponential in theory even though it is dramatically smaller than uninformed search.

• Explicit graph (like road networks): A* expands at most every node once, so it is bounded by Dijkstra: O(E log V) with a binary heap, O(E + V log V) with a Fibonacci heap (the extra log-per-edge in the binary heap comes from decrease-key; the Fibonacci heap makes that O(1) amortized). The heuristic only ever helps — it shrinks the constant, never worsens the bound.
• Space is the real killer. A* keeps the entire open and closed set in memory — O(b^d) in the worst case. This is why large maps trigger memory-bounded variants (IDA*, SMA*, or fringe search) rather than vanilla A*.
• Priority-queue ops dominate the constant: each of up to E edge relaxations may push to the heap (O(log V)), and V extract-mins cost O(log V) each. Lazy-deletion heaps trade a larger heap for O(1) decrease-key avoidance and usually win on real hardware.

The takeaway: A*'s complexity is data-dependent. Quote O(b^d) for the abstract tree, O(E + V log V) for a finite graph, and remember that a good h shifts the effective branching factor toward 1.

Where it runs at scale: GPS, games, and robots

Game pathfinding is A*'s native habitat. Nearly every RTS, RPG, and shooter runs A* over a navigation mesh or grid; the classic reference is Amit Patel's Red Blob Games tutorials and the recastnavigation/Detour library used across the industry. Grids use Manhattan or octile heuristics; Jump Point Search (JPS), an A* optimization for uniform-cost grids, prunes symmetric paths and can be an order of magnitude faster with no loss of optimality.

Road routing at continental scale can't afford to touch every node, so production engines layer preprocessing on top of A*'s idea. Contraction Hierarchies (Geisberger et al., 2008) and ALT (A*, Landmarks, Triangle inequality — Goldberg & Harrelson) precompute better heuristics; ALT stores exact distances to a few landmark nodes and uses the triangle inequality to build a far tighter admissible h than straight-line distance. These are the algorithms behind OSRM, GraphHopper, and the shortest-path cores of navigation apps.

• Robotics & motion planning: A* over grid/lattice representations; D* and D* Lite (Stentz; Koenig & Likhachev) incrementally repair the A* path when the robot discovers new obstacles — the algorithm on the Mars rovers' local planners.
• AI planning & puzzles: the 15-puzzle and Rubik's cube use A*/IDA* with pattern-database heuristics; Korf's 1985 IDA* first solved random 15-puzzles optimally.
• Standard references: Russell & Norvig, Artificial Intelligence: A Modern Approach, Ch. 3; the original Hart–Nilsson–Raphael paper, IEEE Trans. SSC, 1968.

Pitfalls, edge cases, and variants

A* is easy to get subtly wrong. The failure modes cluster around the heuristic and the queue.

• Inadmissible heuristic ⇒ wrong answer. If h overestimates anywhere (e.g. Euclidean distance while movement is grid-restricted and you forgot the scale, or a hand-tuned weight), A* may return a suboptimal path and never notice. This is the single most common bug.
• Admissible but not consistent. Then f can decrease along a path and a node may be reached more cheaply after it was closed. You must allow re-opening closed nodes (or drop the closed set) to preserve optimality. Consistency ⇒ admissibility, but not vice-versa.
• Weighted A*. Order by f = g + ε·h with ε > 1. This gives up optimality but bounds it: the returned path costs at most ε·C*, and search is much faster. Games and real-time planners lean on this constantly.
• Negative edge weights break A* (and Dijkstra). The g-monotonicity argument collapses; use Bellman–Ford instead.
• Memory blowup. On huge state spaces the open set exhausts RAM. IDA* replaces the queue with iterative-deepening DFS bounded by increasing f-limits, cutting space to O(d) at the cost of re-expanding nodes; SMA* caps memory and forgets the least-promising leaves.
• Floating-point ties. Euclidean h produces many near-equal f values; unstable tie-breaking causes the classic "ant crawling around a diagonal wall" behavior. Add a tiny deterministic tie-break (prefer higher g, or a lexicographic nudge).

A* vs. the classic uninformed alternatives on a graph with V nodes and E edges

Algorithm	Ordering key	Optimal?	Time (typical)	Uses heuristic?
Dijkstra	g(n) only	Yes (w ≥ 0)	O(E + V log V)	No
Greedy best-first	h(n) only	No	O(E) but often bad	Yes
A*	g(n) + h(n)	Yes (h admissible)	≤ Dijkstra, often ≪	Yes
BFS	depth	Yes (unit cost)	O(V + E)	No
IDA*	g(n) + h(n)	Yes (h admissible)	O(b^d), O(d) space	Yes