How Bidirectional Search Works
Bidirectional search grows one search from the start and another from the goal and stops when they meet. Two small circles cover far less of a city than one big one, and with the right stopping rule the route is still the shortest.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(d) | O((V + E) log V) | O((V + E) log V) | O(V) |
The asymptotic bound does not move; the saving is in the constant. Two searches of radius r/2 cover about half the area of one search of radius r.
How bidirectional search works
Run Dijkstra forward from the start on the streets and backward from the goal, always advancing whichever side has the smaller key. Every time one side reaches an intersection the other has already seen, a candidate route exists; remember the best one. The subtle part is when to stop: not when the two searches first touch, but when the smallest keys on both sides add up to at least the best candidate, because only then can no untouched route be shorter. Bidirectional A* adds a heuristic to each side; averaging the two heuristics, p(v) = (h_goal(v) - h_start(v)) / 2, keeps both sides consistent with each other so the same stopping rule stays correct.
- Start one priority queue at the start and one at the goal. The best route so far is infinite.
- Advance the side whose smallest key is lower: settle that intersection and relax its streets.
- Whenever a relaxed street reaches something the other side has a distance for, the sum of the two distances plus the street is a complete route. Keep the shortest one seen.
- Stop when the forward and backward keys at the top of the two queues add up to at least that best route. Stitch the forward parents and the backward parents together at the meeting street.
When to use it
- Use it for single-pair queries on large graphs where the goal is known and the edges can be walked backward - road networks are the textbook case.
- Pair it with a heuristic on both sides (bidirectional A*) for the biggest saving, but use the averaged potentials or the stopping rule breaks.
- Skip it when the backward graph is hard to build, or when there are many possible goals.
The lab has both versions. Bidirectional Dijkstra paints two circles, blue from the start and purple from the goal; bidirectional A* paints two narrow wedges that point at each other. Both return exactly the route Dijkstra returns.
Check yourself
Why is stopping as soon as the two searches meet wrong?
The first intersection both sides reach is not necessarily on the shortest route: a slightly longer street to a not-yet-met intersection can still produce a shorter total. Only when the two queue tops sum to the best route found can nothing unseen beat it.