Bidirectional Search Visualization & Simulator

About this visualization

Bidirectional search grows two breadth-first searches at once, one forward from the start and one backward from the goal, and stops when they meet. Each only needs to reach about half the depth, so the work drops from $O(b^{d})$ to roughly $O(b^{d/2})$ .

How it works

Grow one search from the start and another (along reversed edges) from the goal.
Expand a full level of the smaller frontier each time.
When a node is reached by both searches, join the two half-paths.

Formulas used

Time and space: $O\!\left(b^{d/2}\right)$

Worked example

On the 3 × 5 grid from corner A to corner O (6 steps apart), each search only needs to go about 3 steps. The searches meet in the middle and the joined path has 6 edges, found after expanding 12 nodes instead of the 14 that a single breadth-first search needs.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Worst case	$O(b^{d/2})$
Space	$O(b^{d/2})$

Complete and edge-optimal with breadth-first search on both sides. Needs a single, known goal and reversible moves.

When to use it

Shortest-path problems with a single known goal.
Social-network distance (degrees of separation).
Understanding exponential savings in search.

Frequently asked questions

Why is bidirectional search faster?

Two searches of depth d/2 explore about 2·b^(d/2) nodes, far fewer than one search of depth d, which explores b^d.

What do you need for bidirectional search?

A single explicit goal state, and the ability to search backwards (predecessors of a node).

Is bidirectional search optimal?

With breadth-first search on both sides it finds a path with the fewest edges.