An estimate is a reweighting

A* is usually taught as an extension of Dijkstra’s algorithm: the same loop, with the key of a vertex changed from the distance travelled to the distance travelled plus an estimate of the distance remaining. Its correctness is then proved separately, with a lemma about the estimate — that it is admissible, never exceeding the true remaining distance — and a second, stronger lemma for the case where the estimate is consistent, never dropping across an arc by more than the arc costs.

That presentation hides something. A* with a consistent estimate is not an extension of Dijkstra’s algorithm. It is Dijkstra’s algorithm, run on a graph whose arcs have been repriced, and the two lemmas are Dijkstra’s precondition and its failure. This page checks the identity by running both, and then breaks the precondition on purpose to measure what the failure costs.

The identity #

Take any function $h$ on vertices and replace every arc’s cost by its reduced cost:

$$w_h(u, v) = w(u, v) + h(v) - h(u).$$

Along any path from $s$ to $t$ the added terms telescope: each intermediate vertex’s $h$ is added once and subtracted once, leaving $h(t) - h(s)$. So every path from $s$ to $t$ has its cost changed by the same constant, and the shortest path does not move. Nothing about which route is best depends on $h$.

Now run Dijkstra’s algorithm from $s$ on the reduced costs. A vertex $v$ is taken off the queue in order of its reduced distance, which is its true distance plus $h(v) - h(s)$. The $h(s)$ is the same for every vertex, so the order is the order of true distance plus $h(v)$ — which is exactly A*'s key. The two searches take vertices off their queues in the same order, expand the same vertices, and stop at the same moment.

And Dijkstra’s algorithm on the reduced costs is correct precisely when every reduced cost is non-negative, which is $w(u,v) + h(v) - h(u) \ge 0$, or $h(u) \le w(u,v) + h(v)$ — the definition of consistency, letter for letter. The bound with a precondition measured what Dijkstra’s precondition buys; consistency is that precondition, written in terms of the estimate.

The counts agree exactly, which is the first half of the check. The second half is that the searches agree in order, not merely in total — two different algorithms could expand the same number of cells by coincidence.

The two panels are identical, and the site’s check requires them to be: it runs both searches on the same grid and fails if either the expansion count or the path differs. That is a stronger statement than the lemma in a textbook, because it is checked on a concrete instance with a concrete tie-breaking rule, and a subtle difference — a heap that breaks ties differently when keys are offset by a constant — would show up as a different shading.

Why this is the more useful way to see it #

The identity changes where the difficulty of A* is located, and it connects it to a construction this ladder already has.

It says the estimate is a potential. A function whose differences reprice arcs without moving shortest paths is called a potential, and potentials are the standard tool for handling negative arcs. Johnson’s algorithm runs Bellman–Ford once to compute a potential that makes every reduced cost non-negative, then runs Dijkstra from every source on the reduced costs. A graph is as hard as its largest cycle ended on exactly that construction. A* is the same construction with the potential supplied by the caller — chosen to point towards one goal, so that the reduced costs are small along good routes and large along bad ones.

It says why a good estimate prunes. On the reduced graph, an arc’s cost is how much further it takes a path from the goal than the estimate expected. Along a route the estimate predicts perfectly, every reduced cost is zero, so Dijkstra walks straight to the goal. Everywhere the estimate is too low, reduced costs are positive, and Dijkstra spreads out to compensate. An estimate borrowed from an easier problem measured the straight-line estimate collapsing on weighted terrain; on the reduced graph that collapse is every arc keeping most of its original cost, because the estimate took almost nothing off.

And it says exactly what goes wrong when the estimate is not consistent. Some reduced costs are negative, Dijkstra’s precondition fails, and the familiar consequence of running Dijkstra on negative arcs follows: a vertex can be finalised at a distance that a later, cheaper route would have improved.

The two ends of the dial, and the weighted search between them #

The reduced-cost view puts every estimate on one line, and two points on that line are worth stating because they bracket everything measured here.

The estimate that is zero. Every reduced cost equals the original cost, and the search is plain Dijkstra — 543 cells on the grid above. No information, no pruning, and no risk.

The estimate that is exact. If $h(v)$ is the true remaining distance from every vertex, then every arc on some shortest path to the goal has reduced cost exactly zero, and every other arc has a positive one. Dijkstra on those costs walks along zero-cost arcs and never has a reason to leave them, so it expands only vertices on shortest paths. Perfect information, perfect pruning — and computing it is the whole problem.

Every useful estimate lies between, and the reduced costs say precisely where: an arc’s reduced cost is the amount by which taking that arc disappoints the estimate. A good estimate leaves little disappointment along good routes and a lot along bad ones.

The same view explains the weighted search the precondition on a function the caller writes measured. Scaling a consistent estimate by a weight $w > 1$ gives reduced costs $w(u,v) + w\,h(v) - w\,h(u)$, and since a consistent estimate can drop by the full cost of an arc, the scaled one can drop by $w$ times that — so some reduced costs go negative. Weighted A* is Dijkstra on a graph with negative arcs, run without reopening, and its well-known guarantee — a path within a factor $w$ of the shortest — is a bound on how much damage those particular negative arcs can do. The inconsistent estimate below produces negative arcs with no such structure, and so no such bound.

Consistency is the property a caller can check #

There is a practical asymmetry between the two lemmas that the textbook order obscures. Admissibility is the property A* is usually said to need, and it is a statement about the true distance from every vertex to the goal — which is the thing the search is trying to compute. A caller cannot check that an estimate is admissible without solving the problem the estimate was meant to help with.

Consistency is a statement about each arc separately: $h(u) \le w(u,v) + h(v)$. It can be checked by one pass over the arcs, in time proportional to the graph, with no search at all. And it implies admissibility, since summing it along a shortest path from any vertex to the goal gives $h(v) \le d(v, t) + h(t)$, and $h(t)$ is zero.

So the property that is usually treated as a technical strengthening is the one that can actually be verified, and the reduced-cost search verifies it for free: its count of arcs priced below zero is zero exactly when the estimate is consistent on every arc it scanned. The definition is not the algorithm is the theme for results like this — the definition of a correct estimate is admissibility, and the algorithm’s needs, and a checker’s reach, are both consistency. A distance that is not a distance is the same situation for string costs, where the property a pruning structure needs is the triangle inequality, it is checkable triple by triple, and a cost matrix that fails it silently breaks the structures built on it.

An estimate that is never too high and still breaks the search #

Constructing an admissible but inconsistent estimate is easy, and the one used here is deliberately artificial so that its failure has an obvious cause. Take the straight-line estimate and set it to zero on every cell whose coordinates sum to an odd number. It is still a lower bound everywhere — zero is below any distance, and the straight line was already below the truth. But between two neighbouring cells it can drop from the full straight-line distance to zero, which is far more than the one-unit step between them, so it is not consistent.

The plate is surprising at first sight. The search that refuses to reopen cells expanded fewer cells than the consistent A* did — 164 against 325 — with a strictly less informative estimate, and returned the right answer. The search that allowed reopening expanded 362, more than the consistent search, and reopened eleven cells along the way.

The low count is not an achievement. It is the symptom. A search that finalises cells at distances a later route would have improved, and never looks back, closes cells early and so appears to do less work. On this grid the cells it closed early happened not to lie on the shortest path, so the error did not reach the answer. The reopening search is doing the work that correctness requires.

The reduced costs that went negative #

The identity does not care whether the estimate is consistent. Dijkstra on the reduced costs, skipping finished vertices as Dijkstra always does, is still A* without reopening, and it still expands exactly 164 cells. What changed is that 215 of the arcs it scanned had negative reduced costs.

That count is the precondition’s failure made concrete. Every one of those arcs is a place where the estimate dropped by more than the step cost, and every one is a place where Dijkstra’s argument — that a vertex taken off the queue can never be reached more cheaply later — is not guaranteed. On a checkerboard, half the cells are the high side of such a drop, so there are many of them.

Put side by side with the control, the price is plain. Reopening makes the inconsistent search correct, and it costs 362 expansions against the consistent estimate’s 325 — a worse estimate paid for twice, once in the information it lacks and again in the reopenings it causes. It still beats no estimate at all by a wide margin, which is why admissible-but-inconsistent estimates are used: they are sometimes much easier to construct than consistent ones, and reopening rescues them.

A grid where the search that does not reopen is wrong #

This is the counterexample the unit-cost grid did not provide, and it is the one the site’s check is built on: a search with an estimate that never overestimates, run without reopening, returning a path 5% longer than the shortest. Nothing is wrong with the implementation. The algorithm, as stated — take the smallest key, never revisit a finished vertex — is not correct for this estimate, and the instance proves it.

The reopening search needed 70 reopenings here, against 11 on the unit grid. Terrain makes the estimate’s drops matter more, because a cell finalised too early on weighted ground can be off by several units rather than one, and more of the later routes are improvements.

On weighted terrain with an estimate this poor, none of the three is much better than Dijkstra — the checkerboard estimate is zero on half the cells and a fifth of the truth on the other half — so all three panels are nearly full. The difference that matters is not in the number of cells. It is in the last few dozen expansions near the goal, where the non-reopening search reached the goal along a route it had committed to and the reopening search went back.

Why the check has to be able to reject #

This collection has a standing rule that a check must reject: an assertion that has never refused an input proves nothing about the inputs it accepts. This page’s measurements are a small instance of why.

The unit-cost grid is an input on which the non-reopening search is correct. A test suite built from grids like it — unit costs, moderate walls — would pass the non-reopening search forever, and would pass an implementation of A* that silently dropped the reopening branch. The error needs weighted costs and a particular arrangement of walls to surface, and the site’s check names the seed where it does so that the rejection is reproducible rather than hoped for.

The invariant that was wrong for seven years is the long version of the same lesson: a property that holds on every input anyone tried is not the property the algorithm needs, and a proof that assumes the stronger one can survive a very long time. Consistency is the property A* without reopening needs; admissibility is the weaker one that is usually stated.

What the identity does not say #

It says nothing about the order in which ties are broken. Two vertices with equal keys can be taken in either order, and the identity holds for any fixed rule applied to both searches. The check here uses the same heap for both, and a different rule in one of them would make the shadings differ on ties while leaving the counts almost the same.

It says nothing about which potential to choose. Johnson’s potential makes every reduced cost non-negative for every source; A*'s makes reduced costs small towards one goal. Johnson’s is computed by one Bellman–Ford from a virtual source joined to every vertex, so it costs $V \cdot E$ once and serves every query; it is the natural companion to the precondition that removes the queue, which makes the same computation linear when the graph has no cycles. The identity joins them as constructions without saying when computing a potential is worth it. An estimate borrowed from an easier problem measured one answer — landmark tables, computed once, paying for themselves after about five queries — and a landmark estimate is a potential computed from Dijkstra searches rather than from Bellman–Ford.

And the inconsistent estimate here is artificial. Real inconsistent estimates come from taking a maximum over estimates that are individually consistent but computed on different abstractions, or from estimates that are only approximately lower bounds; their negative reduced costs are rarer and less regular than a checkerboard’s. The counts above are therefore the failure at its most visible, chosen so that the cause is unmistakable.

Where this ladder goes next: where two searches should stop #

The reweighting makes a second classic speed-up easy to state and easy to get wrong. Search from both ends at once — forward from the source, backward from the goal on the reversed arcs — and stop when the two searches meet. Two discs of half the radius hold about half the area of one disc of the whole radius, so a two-ended search should expand about half as many vertices.

The trap is the word meet. The obvious stopping rule — stop at the first vertex that both searches have finished, and report the route through it — is wrong, and wrong in exactly the way this page’s non-reopening search was wrong: it commits to an answer at a moment when a cheaper route through an arc between the two frontiers has not yet been examined. The correct rule tracks the best route seen across any arc joining the two searches, and stops only when the two frontiers’ smallest keys together can no longer beat it.

The next rung measures both rules on many grids, counts how often the obvious one returns a longer path, and measures what the correct one saves against a one-ended search — which, as this page found for reopening, is less than the geometry promises, because correctness costs expansions.