Bidirectional search

From Republic Square to the Green Bazaar it is 3.79 km by the streets. To find that out, Dijkstra looks at 1422 crossroads: everything closer to the start than the bazaar. Instead of one wave, send two, one from the square and one from the bazaar. Each only needs to reach the middle of the path, and together they look at 769 crossroads. Below are both waves on the real streets of Almaty. Move the finish by tapping the map, then switch the stop to “Stop on meeting” and press “Find a trap”: a rule that seems obvious gives a wrong answer, and the scene will find a place where this shows.

The orange wave grows from A, the blue one from B. The dashed circles of the same colour are the radii of the waves: neither wave got farther in a straight line, because a road is never shorter than a straight line. The grey dashed line is the circle one wave would have had to fill. The ratio of the areas is the gain, but not the whole of it: where it is larger and where smaller, we will see below.

The idea

A shortest path from A to B of length D can be cut in the middle. A wave from A that has reached radius D/2 and a wave from B that has reached D/2 together cover the whole path. Two circles of radius D/2 have half the area of one circle of radius D, and there are that many times fewer crossroads in them. The path found is glued together from a piece of one wave, one street between the waves, and a piece of the other wave.

An algorithm comes out of this thought, but it involves three decisions, and each is easy to get wrong.

1. Which wave to advance. Both waves are ordinary Dijkstra with its own heap. At each step take a vertex from the heap with the smaller key: then the radii grow equally. You can also alternate the waves in turn or advance the one with the smaller heap; this affects only the speed, not correctness.
2. Along which edges the second wave goes. The wave from B looks for paths into B, not out of it, so it goes along edges against their direction. On a map with two-way streets this is invisible, but in a graph with one-way streets and in a network of flights it is essential.
3. When to stop. Keep μ, the length of the best path from A to B found so far. Every time a wave looks at an edge (u, v) and v already has a label from the other wave, a path A … u → v … B has been found, and if it is shorter, μ is decreased. Stop when the sum of the radii, the smallest keys of the two heaps, reaches μ.

The third decision seems superfluous: why μ and sums, if you can stop where the waves met and answer with the path through the meeting point? It is the first thing that comes to mind, and it is wrong.

The trap: the meeting point

Let the search stop as soon as some crossroads has been taken from the heaps by both waves, and answer with the path through it. Below is such a search step by step on one block near Republic Square: the start A is the corner of Zheltoksan and Timiryazev, the finish B is on Satpayev, east of the square. Orange numbers are distances from A, blue ones from B; bold ones are final. Under the map are the radii of the waves and μ.

The block can be gone round on two sides. The northern side, along Zheltoksan to Satpayev and on along Satpayev, is 1106 m. The southern one, along Timiryazev and up to Satpayev, is 1194 m. On the southern side the waves went faster: the wave from A covers a long stretch of Timiryazev without a single crossroads in one edge. So the first crossroads taken by both waves turned out to be the south-eastern corner of the block, and the path through it is 88 m longer than the shortest.

The waves found the northern path too, and much earlier. Step through until μ becomes 1106: that is the 25th crossroads looked at. The wave from A takes the corner of Zheltoksan and Satpayev and sees next to it a crossroads on Satpayev that the wave from B has already reached. The path is found, and it is the shortest. But neither of the two ends of this short street will ever be taken by both waves: the shortest path is stitched along a street whose ends belong to different waves. The rule “stop at meeting” does not look at such streets.

This is not rare. On 40 random routes across Almaty from the listing below, the rule “stop on meeting” gave a path longer than the shortest 13 times. There the errors are small, up to 0.7 %, while in the block above it is 8 %. The error happens where there are two ways round of almost the same length, and in a city laid out in blocks there are many of them.

Why the right stop is right

Let δ(x, y) be the length of a shortest path, and r_A and r_B the smallest keys in the heaps of the waves. First, one property of ordinary Dijkstra that works for two here.

The proof also explains the trap. The edge on which the shortest path is stitched is found in time, but its ends belong to different waves, and the place of the “meeting” has nothing to do with it. The theorem also gives a soft version of the rule: you may stop when some vertex w has been processed by both waves, if you answer not with the path through w but with the number μ. At that moment r_A + r_B ≥ δ(A, w) + δ(w, B) ≥ μ, so the right rule would already have fired. In the block above it fires at the 53rd crossroads looked at, while the meeting happens at the 72nd: the right stop is earlier as well.

Code

Both waves live in one function: the arrays of distances, heaps and “processed” marks come in pairs, index 0 for the wave from the start and 1 for the wave from the finish. The function top throws stale entries out of a heap and returns the smallest key: the radii are compared from it. The naive flag turns on the wrong rule from the trap, to compare both on the same routes.

Zheltoksan/Timiryazev -> Satpayev
  one wave         1106 m, settled   148
  two waves        1106 m, settled    53
  first meeting    1194 m, settled    72
Republic Square -> Green Bazaar
  one wave         3786 m, settled  1422
  two waves        3786 m, settled   769
  first meeting    3786 m, settled   778

To restore the route itself, keep a parent for each label of both waves and remember the edge on which μ last decreased. From its ends follow the parents: towards A by the parents of the first wave, towards B by those of the second. At the moment of stopping these chains lead along a shortest path: any other path along the parents would be no longer than μ, and there are no paths shorter than μ.

How much is saved

The worst-case bound is the same as Dijkstra's: each wave processes a vertex at most once, so O((V + E) log V) time and O(V) memory, just twice as many arrays. There can even be a loss. If the start is in a sparse network and the finish in a dense one, the circle of radius D/2 around the finish may weigh more than the circle of radius D around the start; on the streets of Almaty this happens rarely, but it happens. The whole gain lies in how the graph is built, and it is convenient to count through the “ball”: how many vertices lie within r of a given one.

Planar networks. On a map a ball is a circle, and the vertices in it are proportional to its area, that is, r². One wave looks at a ball of radius D, two waves at two balls of radius D/2: 2 · (D/2)² = D²/2, half as much. On 40 random routes across Almaty from the listing, one wave looks at 4263 crossroads on average, two waves at 2614: 1.6 times fewer, not 2. There are two reasons. The city ends: a large circle around a start near the outskirts is half empty, and one wave pays less than πD², while the small circles of two waves almost always lie wholly within the city. And the city is uneven: a wave going through the dense centre is heavier than a wave among private houses, while we equalise the radii by length, not by work.

Time gains even less. Two waves have two heaps, two sets of arrays and a check of μ on every edge, and on short routes this eats up the whole gain. The measurement below: the start in the city centre, six finishes at each distance.

On short routes two waves are slower than one, on long ones faster, and the gap grows with distance: the area of a circle grows as D², while the extra work per crossroads is constant. In Go two waves catch up with one by a kilometre and a half and at eight win 2.1 times; in Python, where every extra operation is dearer, by two kilometres, and at eight the gain is 1.5 times. For a navigator computing routes across the whole city and beyond, that is an honest one and a half to two times. Real speed comes not from two waves by themselves but from a precomputation in which two waves are one part: that is what contraction hierarchies are about.

A small world: a root instead of a half

It is quite another matter with networks where the ball grows not as a square but as a power: each next layer has b times more vertices than the previous one. One wave to depth d looks at about b^d vertices, two waves to depth d/2 at about 2b^d/2. That is no longer a half but a square root. Networks of acquaintances, of links on the internet and of air routes are built this way: from anywhere to anywhere is a few steps, and every step multiplies the reach.

Below is the air network of the whole world: 3468 airports and 84,869 flights from the call-sign database of Virtual Radar Server. Only airports from which you can fly to any other and back are taken. We look for a route with the fewest flights: this is breadth-first search. The wave from B flies along the routes backwards: it looks for where you can fly into B from.

From Almaty to Queenstown is three flights. To find that out, one wave marks 3030 airports of 3468: in three steps it goes round almost the whole world. Two waves mark 185. Over 300 random pairs of airports one wave marks 1667 on average, two waves 143, 11.7 times fewer. And that is on a network of only three and a half thousand vertices; the larger the network, the bigger the difference between b^d and 2b^d/2. Notice the exception too: for a direct flight to Astana both waves need 57 marks each; one layer from A is already enough, and the second wave has nothing to save.

In an unweighted graph the stop can be simplified. If the waves are expanded by whole layers, the one with the smaller layer first, then the very first touch, an edge from a new vertex of one wave to a marked vertex of the other, gives a shortest path. While there have been no touches, the marked sets did not intersect: so no vertex lies closer than k_A to A and at the same time closer than k_B to B, where k_A, k_B are the depths of the layers, and a path shorter than k_A + k_B + 1 is impossible. And a touch while expanding layer k_A gives a path of exactly that length. Expanding vertices one at a time, mixed from two queues, and stopping at the first touch no longer works: then the far end may be a vertex of the next layer.

Two A* waves

A* narrows one wave with a hint about the distance to the finish, and bidirectional search replaces one wave with two. It is tempting to add both gains: give the wave from A the hint “straight line to B”, the wave from B “straight line to A”, and leave the rest as it was. Below this is done on the route from Republic Square to MEGA Alma-Ata. Switch between the variants.

“Own hints” look at only 559 crossroads, half as many as one A* wave, and find a path 320 m longer than the shortest. What broke: the key in an A* heap is not a radius but an estimate of the length of the whole path through the vertex, from A to B. The sum of two such keys is about twice the length of the path, and the rule “sum of keys ≥ μ” fires as soon as any path at all has been found. It is the same stop on meeting, only disguised.

The deeper reason is that the two waves measure with different rulers. A* is Dijkstra on a graph where the length of each edge (u, v) is replaced by the reduced length w − h(u) + h(v) (this is proved in the article on A*). The wave from A has the hint h_B, the wave from B, which goes along edges in reverse, h_A, and the same edge gets different reduced lengths in the two waves. The proof of the right stop relied on both waves counting in the same units. There are two ways to restore this.

Pohl's stop. Leave the waves their hints, and stop when the smallest key of one of the heaps has reached μ. Each A* wave on its own is an honest search: while its heap has a key smaller than μ, a path shorter than μ may still be found, and when it has none, it cannot. This is correct but slow: the search waits until one of the waves has done almost all the work alone. On the scene's route it is 2379 crossroads, twice as many as one A* wave.

Averaged hints. Give both waves one ruler. Take the potential

$$p(v) = \frac{h_B(v) - h_A(v)}{2}$$

and put the key d_A(v) + p(v) into the heap of the wave from A, and d_B(v) − p(v) into the heap of the wave from B. Such hints are called consistent with each other: their sum is constant (zero here).

Adding the two gains does not work here either. Each wave gets only half of its own hint and half of the other's with a minus sign, so it is pulled towards the goal more weakly than a single A* wave. On the scene's route it is 1001 crossroads against 1063 for one A* wave. The listing compares all the variants on the same 40 random routes as the first listing.

                               settled  longer  worst  met at best at
one wave, Dijkstra                4263       0   0.0%
one wave, A*                      1009       0   0.0%
two waves, Dijkstra               2614       0   0.0%     92%     94%
two waves, A*, own hints           570      21  10.6%    100%    100%
two waves, A*, Pohl's stop        1986       0   0.0%     30%     34%
two waves, A*, averaged hints      853       0   0.0%     88%     92%

Own hints were wrong on 21 routes of 40, by up to 10.6 %. Pohl's stop is correct but looks at twice as much as one A* wave. Averaged hints are correct and beat one A* wave by about 15 %. That is modest, and it is an honest result. Andrew Goldberg and Chris Harrelson compared such variants on large road networks in 2005: the straight-line hint gave them almost nothing for either one wave or two, while with landmark hints (that very ALT from the article on A*) two waves with averaged potentials overtook one, by more than twice on long routes and by less than one and a half times on short ones.

The last two columns answer an old dispute. “Met at” is the share of the work done when the waves first touched and the first μ appeared. “Best at” is when μ became final. With Pohl's stop the waves meet having done 30 % of the work, the best path is found by 34 %, and the remaining two thirds of the work go into making sure there is nothing shorter. Ira Pohl combined two waves with hints in 1971 and found that such a search is worse than a single one. Pohl explained this with a picture of two missiles that fly towards each other and pass without meeting; Nils Nilsson reprinted it in a 1980 textbook, and the explanation took root. In 1997 Hermann Kaindl and Gerhard Kainz showed that it is wrong: the waves meet early, and the main work is spent after the meeting, on finding the best path and on proving there is no better one. In their experiments on the fifteen puzzle the first path was found on average after 7 % of all the work, the optimal one after 22 %, and the rest went into checking. The table above shows the same on the streets of Almaty.

Where it is used

• Navigators. Two waves rarely walk the raw road graph, but they are almost always inside fast methods. A query in contraction hierarchies is two Dijkstra waves, from the start and from the finish, which climb only to more important crossroads and meet at the top. The best path is also kept in μ there, and they stop in their own way; more on that in the article on hierarchies.
• Networks of links. The site Six Degrees of Wikipedia finds shortest chains of links between two articles with bidirectional breadth-first search; the search file in its source code begins with these words. The waves are expanded by whole layers, each time the one with fewer links in its next layer. The second wave goes along links backwards, so the site keeps both outgoing and incoming links for each article.
• Puzzles and search. When the state space grows exponentially, two waves of depth d/2 instead of one of depth d turn an impossible search into a possible one. The same trick without a graph is meet in the middle: search the halves of a problem separately and match them.

History

In 1966 T. Nicholson published the paper “Finding the shortest route between two points in a network” in The Computer Journal. His method led routes from the beginning and from the end at once and each time extended those that had gone the least, the same two waves chosen by radius. And the main point is already there: when the first full route has been found, the work is not over; you still have to make sure it is the shortest.

In 1969 Ira Pohl defended a thesis on bidirectional and heuristic search, and in 1971 published the paper “Bi-directional search”. Surveys credit Pohl with the proof that bidirectional Dijkstra with μ remembered finds a shortest path. The same paper tried adding hints to the waves, and got that very unsuccessful result which was then explained with missiles for a quarter of a century.

Averaged potentials were proposed in 1994 by T. Ikeda and co-authors, at a conference on vehicle navigation. In 2005 Goldberg and Harrelson divided the ways of combining A* with two waves into symmetric ones (each wave has its own hint and Pohl's stop) and consistent ones (a common ruler), and by the number of vertices looked at the consistent variant with landmarks came out best. And in 2024 Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan and Jakub Tětek proved that a carefully built bidirectional search is optimal on every single graph: in their model no correct algorithm can examine fewer edges on it by more than a constant factor.

Problems

In the first problem you need two complete waves, from the start and towards the finish along reversed one-way streets, to find out which crossroads you can drop by on the way. In the second, thousands of queries about connections in the world air network, where one wave will not make it in time, and two waves expanded the wrong way are off by one.