A* and the Conditions on a Heuristic

Dijkstra’s algorithm expands a frontier that depends only on the source, so it explores a roughly circular region of the graph and stops when the destination happens to fall inside it. On a road network, a query from one suburb to another across a city expands a disc whose area is proportional to the square of the distance travelled. A* replaces the key $d[v]$ with $d[v] + h(v)$, where $h$ estimates the remaining cost to the goal, and the frontier becomes an ellipse stretched toward the destination. The transformation is one line of code, and the conditions under which it preserves correctness are the whole subject.

The two conditions

Let $h(v)$ be the heuristic estimate of $\delta(v,t)$, the true distance from $v$ to the target $t$, and let $c(u,v)$ be the edge weight.

Admissibility: $h(v) \le \delta(v,t)$ for all $v$, with $h(t) = 0$. The estimate never overstates the remaining cost.

Consistency, also called monotonicity: $h(u) \le c(u,v) + h(v)$ for every edge $(u,v)$, and $h(t) = 0$. The estimate cannot drop by more than the edge cost when moving along an edge.

Consistency implies admissibility, by induction along a shortest path: summing $h(v_i) \le c(v_i, v_{i+1}) + h(v_{i+1})$ from $v$ to $t$ gives $h(v) \le \delta(v,t)$. The converse fails, and the gap matters: an admissible but inconsistent heuristic produces correct distances only if the implementation is willing to reopen closed nodes.

The Euclidean distance to the goal, in a graph whose edge weights are Euclidean lengths, satisfies both conditions with equality along straight lines. For a graph with edge weights that are travel times rather than distances, Euclidean distance divided by the maximum speed on any edge is consistent only if no edge is faster than that maximum, a bound that has to be derived from the data rather than assumed.

Why consistency removes reopening

A* maintains a closed set of expanded vertices. With a consistent heuristic, once a vertex is expanded its label is final, and the argument is a small adaptation of the one in Dijkstra and the Settled-Set Invariant.

Suppose vertex $u$ is expanded with key $f(u) = d[u] + h(u)$, and suppose a cheaper route to some vertex $v$ in the closed set were later found. Along that route, at the moment it first leaves the closed set, let the crossing edge be $(x,y)$ with $x$ closed and $y$ open. Then $f(y) = d[y] + h(y) \le d[x] + c(x,y) + h(y) \le d[x] + h(x) = f(x)$, using consistency. Since $x$ was expanded, $f(x) \le f(u)$ by the order of expansion. So $f(y) \le f(u)$, and $y$ would have been expanded before $u$, which is a contradiction. Hence no cheaper route into the closed set exists, and closing a vertex is safe.

With mere admissibility the middle inequality is unavailable, $f$ can decrease along a path, and a closed vertex can be improved. The standard repair is to keep vertices in the open set after expansion and allow re-expansion when a better label arrives; on graphs where the heuristic is badly inconsistent this can expand the same vertices many times over. Dechter and Pearl showed that admissibility alone is sufficient for optimality of the solution when the algorithm is allowed to reopen, which is why the distinction is stated as a condition on implementations rather than on results.

The shape of the expansion

The set of expanded vertices is ${v : f(v) \le C^}$ where $C^$ is the optimal cost, for a consistent heuristic and a graph where ties resolve favourably. So the work is governed by how many vertices lie within an $f$-contour.

Two consequences follow. First, the heuristic’s informedness, meaning how close $h$ is to the true remaining cost, determines the volume directly. With $h \equiv 0$ the contour is a ball around the source and the algorithm is Dijkstra. With $h = \delta(\cdot,t)$ exactly, every vertex on a shortest path has $f = C^*$ and the expansion is confined to the optimal paths; but computing $h$ exactly is the original problem, so exactness is only available when it comes from preprocessing.

Second, the contour’s shape, not just its volume, is what makes A* useful on road networks. The ellipse has area proportional to the squared distance but with an eccentricity set by the heuristic’s accuracy; a perfect distance estimate would collapse it to a line.

Weighted heuristics and bounded suboptimality

Multiplying the heuristic by $w > 1$ inflates the contour’s forward bias and reduces expansions. The result is no longer guaranteed optimal, but it is guaranteed to be within a factor of $w$ of optimal. The argument is short: for any vertex $v$ on an optimal path, $f(v) = d[v] + w,h(v) \le d[v] + w,\delta(v,t)$, and at the source this is at most $w,C^$. So the search never expands anything with $f$ above $w,C^$, and the goal is found with a cost no greater than that.

That is a real, checkable guarantee, and it is the reason weighted A* is used where a modest suboptimality is acceptable in exchange for a large reduction in expansions. The cost is not merely “some suboptimality”: the returned path can differ from the optimal one in structure, not just in a few percent of weight, and the bound is tight in the worst case. A value of $w$ slightly above 1 is often indistinguishable in output; large values converge to greedy best-first search, which ignores accumulated cost entirely and can produce paths far longer than optimal while expanding very few vertices.

Making a heuristic from preprocessing

Since informedness drives everything, the useful heuristics are the ones derived from the graph offline. The landmark method, known as ALT, for A*, landmarks, and triangle inequality, picks a small set of landmark vertices, precomputes distances from each landmark to every vertex, and uses the triangle inequality to bound the distance between two arbitrary vertices:

$$h(v) = \max_{L} \big|, d(L,t) - d(L,v) ,\big|.$$

The bound is admissible because $d(L,t) \le d(L,v) + d(v,t)$ and $d(L,v) \le d(L,t) + d(t,v)$ both hold in an undirected graph, giving $|d(L,t) - d(L,v)| \le d(v,t)$. Consistency also holds: the expression is a maximum of functions each satisfying the triangle inequality, and a maximum of consistent heuristics is consistent. The precomputation is one Dijkstra run per landmark, and the query cost is one subtraction and comparison per landmark per expansion, a handful of arithmetic operations, which is why the method is attractive when memory for landmark tables is available but a full preprocessing hierarchy is not. On directed graphs the symmetric bound fails and the method needs distances in both directions, which doubles the tables.

The quality depends entirely on landmark placement. Landmarks near the corners of the graph give better bounds than landmarks clustered in one region, and the usual approach is a farthest-point heuristic that picks each new landmark to maximise its distance from the current set.

The implementation hazards

Three failure modes account for most incorrect A* code.

The first is a heuristic that silently violates admissibility because of scale. Mixing units, such as a heuristic in metres against edge weights in seconds, produces a bound that is wrong by a constant factor, and the failure is not a crash but a plausible-looking suboptimal path.

The second is integer overflow in $d[v] + h(v)$. Both terms can be large, and the sum is only used for ordering, so the natural instinct is to use a narrow type; the wrap-around then inverts the ordering of a few entries and the expansion order becomes subtly wrong.

The third is the goal test applied at generation rather than at expansion. Returning a path as soon as the goal is generated is optimal only under consistency; under plain admissibility the generated path can be beaten later, and the returned answer is suboptimal without any diagnostic.

A* also inherits everything from the queue design in Priority Queues for Dijkstra, with one addition: the bucket trick requires monotone keys, and monotonicity of $f$ requires consistency. An admissible but inconsistent heuristic breaks bucket queues outright, because the scan pointer cannot advance.

What the heuristic cannot supply

The heuristic cannot fix the graph’s intrinsic difficulty. On a road network with a poor heuristic, the ellipse still covers a large fraction of the network, and the preprocessing methods in Contraction Hierarchies and Preprocessing for Road Networks reduce query work by orders of magnitude more than any admissible heuristic can. A* also gives no advantage over Dijkstra for one-to-all queries, since there is no single target to aim at; and its memory is the frontier, which on a large graph can dominate. Bidirectional search addresses the frontier size by growing two smaller frontiers instead of one large one, with its own subtleties about when the two searches may stop.