Bidirectional Search and the Problem of Knowing When to Stop

Searching from both ends at once is an old idea with an old trap. The two frontiers meet quickly, and the first meeting point is usually not on the optimal path. An implementation therefore carries an explicit stopping rule and a separate step that extracts the answer, and the correctness of the whole method rests on that rule rather than on the meeting.

What the two searches compute

Run the Dijkstra loop from $s$ on the graph and from $t$ on the graph with every edge reversed. The forward search maintains $d_f[v]$, an upper bound on $\delta(s,v)$; the backward search maintains $d_b[v]$, an upper bound on $\delta(v,t)$. Both are valid for nonnegative weights, and both inherit the settled-set argument from Dijkstra and the Settled-Set Invariant.

Reversing the edges is a storage decision, not an algorithmic one. A directed graph needs either a second adjacency array holding predecessors, or an adjacency array whose entries record both directions. For graphs in the hundreds of millions of edges the duplication is significant, and the choice between doubling memory and paying a transpose cost at query time is the first practical constraint on the method.

The searches must interleave. If the forward search runs to completion before the backward one starts, nothing has been gained. The usual policies are to alternate strictly, to expand whichever side has the smaller frontier, or to expand the side whose minimum key is smaller. Strict alternation is simplest and is what the correctness argument below assumes; the adaptive policies change the work, not the answer, provided the stopping rule accounts for both queues.

Why the first meeting is not the answer

Take an undirected graph with four vertices and four edges: $s$–$a$ of weight 1, $a$–$t$ of weight 10, $s$–$b$ of weight 6, and $b$–$t$ of weight 6. The two $s$–$t$ paths cost 11 through $a$ and 12 through $b$, so the answer is 11.

The forward search settles $a$ at 1 and $b$ at 6. The backward search settles $b$ at 6 and $a$ at 10, because from $t$ the edge to $b$ is cheaper than the edge to $a$. Alternating between the two sides, $b$ becomes the first vertex settled by both, and its label sum is $6 + 6 = 12$. The optimal path crosses at $a$, whose sum is $1 + 10 = 11$, but $a$ is settled by the backward search only after $b$ is. Stopping at the first doubly settled vertex returns 12.

The example shows what the rule ignores: the two searches advance at their own rates, and the vertex they reach first from both ends is the one that minimises the larger of its two labels, not the one that minimises their sum. In this instance the first meeting is $b$ with $\max(6,6) = 6$ against $a$ with $\max(1,10) = 10$. A cheap rule on a metric that is not the objective produces a wrong answer, and it does so on a graph with four edges and no degenerate structure.

The rule is safe only under additional assumptions about balanced progress, which are properties of the input and the expansion policy rather than of the code. That makes it a source of intermittent failures rather than a simplification.

Safe stopping rules

Two rules are provably safe, and they differ in tightness.

The conservative rule: keep a running best complete path $\mu$, and stop as soon as the minimum key in either queue reaches $\mu$. At that moment every remaining unsettled vertex has $d_f \ge \mu$, so no route through one of them can beat $\mu$, and $\mu$ is optimal. This rule is easy to justify and easy to get wrong only in the direction of stopping too late.

The tight rule: stop when $\min(\text{key}_f) + \min(\text{key}_b) \ge \mu$. The justification is that any undiscovered $s$–$t$ path must cross from the forward-unsettled region into the backward-unsettled region at some edge $(x,y)$ with $x$ not settled forward and $y$ not settled backward; its length is at least $d_f[x] + w(x,y) + d_b[y] \ge \text{key}_f + \text{key}_b$. If that sum reaches $\mu$, nothing undiscovered can improve on $\mu$. This rule expands strictly fewer vertices and is the one to implement. Note that it requires both searches to be Dijkstra with nonnegative reduced costs; with a heuristic in play, the keys include $h$ and the argument needs adjusting, as discussed below.

Both rules require $\mu$ to be maintained continuously. Every time a relaxation on one side produces a vertex whose label on the other side is already finite, the candidate $\mu = d_f[v] + d_b[v]$ is tested. In practice $\mu$ is updated during relaxation rather than during extraction, because a vertex may never be extracted on one side before the search stops.

Recovering the path

The meeting vertex that produced $\mu$ is the split point. Reconstruct the forward half by walking predecessor pointers from that vertex back to $s$, and the backward half by walking the backward predecessors to $t$, then join them. This works because both halves are shortest paths to and from the split vertex respectively: the forward predecessor chain records the edge that set $d_f$, and each step of the chain corresponds to a relaxation that was optimal at the time.

A subtlety arises when the optimal path’s crossing edge $(x,y)$ is a graph edge whose endpoints were settled on opposite sides but where no vertex is common. In that case the split point is the edge itself: the path is the forward chain to $x$, the edge, and the backward chain from $y$. Implementations that only track vertex-based candidates miss such paths entirely, which is one of the ways a bidirectional routine returns a path longer than the distance it reports.

The size of the win

For a search that expands a region of radius $r$ in a graph where expansion is roughly isotropic, unidirectional Dijkstra expands on the order of $r^2$ vertices. Two searches each of radius $r/2$ expand about $2 \cdot (r/2)^2 = r^2/2$, a factor of two, and only a factor of two, because the area of a disc grows quadratically while the perimeter shrinks linearly. This is the honest account of bidirectional Dijkstra: the gain is a constant, not an asymptotic improvement, and on graphs where the frontier is not disc-shaped the constant can be worse than 2.

The picture changes with a heuristic. A*‘s expansion region is an ellipse whose area is roughly proportional to the product of the source-to-goal distance and the ellipse’s width. Splitting the search into two half-length ellipses reduces the product by more than a factor of two, and the combination, bidirectional A* with a consistent potential on both sides, is where the technique earns its place. The conditions on the heuristic are the ones set out in A* and the Conditions on a Heuristic.

Potentials on both sides

Running A* in the backward direction requires a heuristic estimating the distance from the target to each vertex, which in an undirected graph is the same function reversed. In a directed graph it is a different function, and the two potentials must be consistent with each other, not merely each consistent on its own.

The standard construction converts the search into a Dijkstra run on reduced costs. Define a potential $\pi(v)$ and replace each edge weight $c(u,v)$ by $c(u,v) - \pi(u) + \pi(v)$; the reduced costs are nonnegative exactly when $\pi$ is consistent. For a bidirectional search the natural choice is to use a single potential function for both directions, with the forward search using $+\pi$ and the backward search using $-\pi$. If the two sides use independently chosen potentials, the reduced-cost nonnegativity can fail on one side, and the search silently degrades to a label-correcting method driven by Dijkstra’s queue. That degradation is harmless only if closed vertices may be reopened, which the standard implementation forbids.

The failure is invisible in the output because the returned path is still a valid path; it is merely not the shortest one.

Balanced frontiers

Because the two searches compete for the same stopping condition, an unbalanced split wastes work: a search that expands one side far ahead of the other produces a large frontier on that side while the other side’s minimum key stays small, and the tight rule cannot fire.

The remedy is to alternate on the side with the smaller key sum or the smaller frontier, rather than strictly. A stronger version assigns each side a potential that biases expansion toward balance; this is the balanced bidirectional search of Ikeda and others, and it turns the two-sided search into a single search in a product space. The bias must be admissible for the final answer to remain optimal, which restricts how much balancing is allowed.

The practical rule is simpler than the theory: alternate on the side with fewer settled vertices, and verify with the tight stopping rule. That combination is correct for any nonnegative-weight graph and does not require the potentials to be balanced.

Where it does not help

Bidirectional search gives no benefit for one-to-all queries, because there is no second endpoint. It gives little benefit on graphs with highly asymmetric distances, where one direction’s frontier is much larger. And it does nothing about the intrinsic cost of a long-range query on a road network: the factor-of-two saving is small compared with the orders of magnitude that preprocessing achieves, as described in Contraction Hierarchies and Preprocessing for Road Networks.

What it does provide is a template. The stopping rule is the reusable idea: a search can be terminated as soon as a proven lower bound on any remaining candidate reaches the best known upper bound, and that pattern reappears in branch-and-bound, in bidirectional variants of label-setting for constrained problems, and in the goal-directed preprocessing methods that maintain both a forward and a backward index.