Where two searches should stop

A shortest-path search from a source spreads outwards until it reaches the goal, and on a graph that looks roughly like a plane — a grid, a road network — the region it covers is roughly a disc whose radius is the distance to the goal. Two searches, one from each end, each need only reach the middle. Two discs of half the radius cover half the area of one disc of the whole radius, so a search from both ends should do about half the work.

That argument is correct as far as it goes and it leaves out the part that decides whether the method is correct at all: when to stop. A one-ended search stops when it takes the goal off its queue, and Dijkstra’s argument guarantees the goal’s distance is final at that moment. That guarantee is the whole of what the bound with a precondition measured Dijkstra’s algorithm buying with its non-negative arcs: a vertex taken off the queue is never reached more cheaply later, so the first moment the goal is taken off is the moment its answer is known. A two-ended search has no single moment like that. The two searches meet — some vertex is reached by both — long before either could be sure the best route passes through that vertex.

This page measures two stopping rules on many grids, and measures what the method actually saves once the rule is the correct one.

The method is old, and so is the trap. Two-ended search for shortest paths was proposed early in the history of the problem, and the incorrect stopping rule has been rediscovered and written down as correct many times since, because it is the rule the picture of two expanding discs suggests. It is a good example of an algorithm whose idea is simple and whose termination condition is where all of the subtlety lives — the same shape as a boundary that costs nothing finds in a different field, where the interesting cost of a method is entirely at the edge the description skips.

Two searches on a grid where every step costs one #

The two searches alternate: at each step, whichever frontier has the smaller key expands its next vertex. The forward search runs Dijkstra from the source on the graph’s arcs; the backward search runs Dijkstra from the goal on the arcs reversed. Every vertex therefore carries two distances, one from each end, each final once its own search has taken it off its queue.

The saving is real and it is not a half. On this grid the two-ended search expands 428 cells to one-ended Dijkstra’s 543 — about 79% — and the reason is visible in the shading. The walls make the grid a poor imitation of a plane: a disc grown from a corner in a maze is shaped by the corridors, and the two half-discs are not half the area of the whole because the region near the goal happens to be sparsely connected. The geometric argument describes an open plane; a maze is not one.

On a larger weighted grid the ratio is 71%. The ratio moves around from grid to grid, which is why the page reports it over many grids below rather than from one plate. But no grid gets close to the half the argument promised, and the reason for that is not the geometry at all. It is the stopping rule.

The obvious rule, and a grid where it is wrong #

The obvious rule is the one anyone would write first: stop the first time some vertex has been taken off both queues, and report the forward distance plus the backward distance through that vertex. At that moment the vertex’s distance from the source is final and its distance to the goal is final, so the route through it is a real route and its cost is exactly known.

It is a real route. It need not be the shortest.

The failing case has a simple shape. The shortest path from source to goal crosses the middle along some arc $(u, v)$, where $u$ is on the forward side and $v$ on the backward side. The forward search finishes $u$; the backward search finishes $v$; but neither finishes the other’s vertex before some different vertex $x$, off the shortest path, happens to be finished by both. The obvious rule stops at $x$ and reports $d_f(x) + d_b(x)$, which is the length of a real route through $x$ — and the route $d_f(u) + w(u,v) + d_b(v)$ through the arc between the two frontiers was shorter and was never compared.

Nothing about the individual searches is wrong. Every distance either search finalised is correct. The error is entirely in the claim that the first doubly-finished vertex lies on a shortest path, which is a claim about the interaction of two correct searches and is false.

That the wrong rule also expanded more cells on this grid is worth pausing on, because it is the opposite of what a shortcut that trades correctness for speed usually does. The meeting rule waits for a vertex to be finished twice, and on terrain two frontiers can overlap considerably before any single vertex is at the head of both queues. The correct rule, below, can stop before any vertex has been finished by both searches — so it is not merely a stricter version of the obvious one. It is a different condition.

The rule that is always right #

The correct rule keeps one extra number, $\mu$: the cost of the best complete route seen so far. Whenever either search relaxes an arc $(u, v)$ where the far endpoint already has a distance from the other search, it checks whether $d_f(u) + w(u,v) + d_b(v)$ beats $\mu$, and if so updates it. That captures every route that crosses between the two frontiers along an arc, including the one the obvious rule missed.

The search stops when the smallest key on the forward queue plus the smallest key on the backward queue is at least $\mu$. At that moment every vertex not yet finished by the forward search is at least the forward key away from the source, and every vertex not yet finished by the backward search is at least the backward key away from the goal, so any route through an unexplored part of the graph costs at least their sum — which is at least $\mu$. No undiscovered route can beat the best discovered one, and $\mu$ is the answer.

The rule’s correctness argument is about the frontiers, not about any vertex, which is why it can fire before any vertex is finished twice and why the obvious rule’s reasoning does not transfer to it. It is worth writing down the invariant it maintains, because that is what a check can test: at every step, $\mu$ is the cost of some real route, and every route whose cost is below the sum of the two smallest keys has already been seen. The first half makes $\mu$ an upper bound on the answer and the second makes the sum a lower bound on anything unseen, so the moment the lower bound reaches the upper bound, they are equal. It is also the same kind of argument an estimate is a reweighting needed for reopening: a search may only commit to an answer when it can prove that nothing it has not yet examined could improve it, and “the frontiers met” is not such a proof.

Forty grids, and how often the obvious rule is wrong #

One counterexample establishes that the obvious rule is not correct. It does not say how often it matters, and a rule that is wrong on one grid in ten thousand is a different engineering proposition from one wrong on one in ten.

Five grids in forty — one in eight — and the errors are small: one to four units on paths of about two hundred, so at most two per cent. That combination is exactly what makes the bug survive. A test that checked a two-ended search against a one-ended one on a few grids would pass most of the time; a test that checked whether the path was roughly as short would pass always. The errors are rare enough to miss and small enough to excuse.

On unit-cost grids the obvious rule was never wrong in forty tries. That is the plate a test suite built from unweighted mazes would produce, and it would certify the wrong rule. The failure needs arcs of different costs, so that the route through the doubly-finished vertex and the route across the frontier can differ by less than a step — which on these grids never happens when every step costs one, and which says nothing about unweighted graphs in general, only about these.

With fewer walls the failure rate rises to one grid in six. An open grid has more arcs between the two frontiers at the moment they meet, so more chances for the best route to cross along an arc neither search has finished at both ends. That gives the error a direction worth knowing: the obvious rule is most dangerous on exactly the graphs where two-ended search is most attractive, the open, plane-like ones.

What a test of this would have to contain #

Put together, the three sweeps say what a test that can catch the obvious rule needs, and it is more specific than “a few random graphs”.

It needs weighted arcs, because on these grids unit costs never exposed the error in forty tries. It needs many instances, because even on weighted grids the rule is right seven times in eight. It needs an exact comparison with a one-ended search, because the errors are one to four units on paths of two hundred, and any tolerance wider than a single unit misses most of them. And it benefits from open graphs, where the error rate roughly doubles.

A test written by someone who believes the obvious rule is correct is unlikely to contain all four. That is the practical content of this collection’s rule that a check must be shown to reject: the site’s check for the correct rule runs it against one-ended Dijkstra on twenty grids of each kind, and a separate check runs the obvious rule on seed seven and requires it to return 212 rather than 208. If a future change made the obvious rule pass that check, the check would fail, which is the only evidence that the check is testing anything.

Counting on a graph fixed this field’s habit of reporting work on named graph families with seeds stated, and this is a case where the habit is load-bearing for correctness as well as for cost. The rule is wrong on a named seed, and anyone can reproduce the 212.

Why the saving is not a half #

Across the sweeps the correct rule expands 64% to 79% of what one search does. Three things account for the gap to a half, and only one of them is geometry.

The frontiers overshoot. The correct rule cannot stop at the moment the frontiers touch; it must wait until their smallest keys sum to $\mu$. By then each search has expanded a ring of vertices beyond the meeting point whose distances are below its own key, so the two regions overlap rather than meeting at a line.

Alternation is by key, not by size. The search expands whichever frontier has the smaller key, which balances the two searches’ radii rather than the number of vertices each has expanded. Where one end of the query sits in a dense region and the other in a sparse one, balanced radii can mean very unbalanced work.

And the plane is not a plane. A maze channels a search along corridors, and a disc of half the radius in a maze need not hold half the cells of a disc of the whole radius. The saving depends on how the number of vertices within a distance grows with the distance, which is a property of the graph, and a half is what that growth looks like only in two dimensions without obstacles.

A constant factor is the whole of the benefit here, and it varies by graph between a fifth and a third. An estimate borrowed from an easier problem found landmark estimates cutting the same kind of search to between a sixth and a fifteenth of Dijkstra’s work, which puts the two techniques’ constants side by side: a good estimate is worth far more than a second search, and it costs preprocessing where a second search costs nothing but the stopping rule. What O-notation does not say is this collection’s account of why that is not a detail: the two-ended search is in the same class as the one-ended one, its entire justification is the constant, and the constant is a measurement rather than a derivation.

Why this belongs next to the reweighting #

The obvious stopping rule fails for the same structural reason the non-reopening search in an estimate is a reweighting failed. Both commit to an answer on local evidence — a vertex finished, a vertex finished twice — when the property that would justify committing is a bound over everything not yet examined. Both are correct on unit-cost grids and wrong on weighted ones. And both are the kind of error a check must reject exists for: an assertion comparing the two-ended search against the one-ended one is only worth having if it is run on an instance where the wrong rule fails, and the site’s check names seed seven for exactly that reason.

The invariant that was wrong for seven years is the long form of the lesson. An invariant that holds on every input a test suite contains can be a different invariant from the one an algorithm needs, and the difference is invisible until an input separates them. Here the two invariants are “the first doubly-finished vertex is on a shortest path”, which holds on every unit grid above, and “no unexplored route can beat $\mu$”, which is the one that is true.

What the measurement leaves out #

No estimate. Both searches here are plain Dijkstra. Combining two-ended search with A* — an estimate pointing each search at the other end — is the obvious next step and a less obvious one, since each search’s estimate reweights the graph differently and the stopping rule above assumes both searches measure distance on the same arcs.

Alternation by smallest key. Other policies — alternate strictly, or expand whichever frontier is smaller in cells — change the constant and not the correctness, provided the stopping condition is kept. The key-balanced policy is the one whose stopping argument is simplest.

Grids only. A road network is much more plane-like than a maze and the saving there is closer to the geometric one; a social graph, where the number of vertices within a distance grows exponentially, can make a two-ended search save far more than a half, since two small balls hold far fewer vertices than one ball of twice the radius. The factor measured here is a fact about mazes.

Where this ladder goes next: two estimates that must agree #

The natural combination of the last three rungs is a two-ended A*: a forward search guided by an estimate of the distance to the goal, and a backward search guided by an estimate of the distance from the source. It is where each of their lessons collides.

By the reweighting, each search is Dijkstra on arcs reduced by its own potential — and the two potentials are different, so the two searches are running on two different graphs. The stopping rule’s argument added a forward key and a backward key and compared them with a route’s cost, which only makes sense if both keys measure the same arcs. With two different potentials they do not, and the correct rule on this page becomes an incorrect rule for the combination.

The known repair is to give both searches the same reweighting, using the average of the two estimates — half the forward estimate minus half the backward one — which is consistent in both directions whenever the two estimates are. The next rung measures three things on the grids above: that the naive combination of two consistent estimates with the stopping rule from this page does return longer paths, how often; that the averaged potential repairs it; and what averaging costs, since each search is now guided by an estimate half as strong as the one it would have alone.