Bidirectional search

O(b^(d/2))

Bidirectional search speeds up shortest-path finding by searching from both ends simultaneously: one breadth-first wave grows from the start (shown in amber/teal), another from the goal (in violet), and the search finishes the moment they touch. Since each wave only has to travel about half the distance, together they explore on the order of b^(d/2) cells instead of b^d — a dramatic saving on long paths. The shortest path is recovered by stitching the start-side half to the goal-side half at the meeting cell. The subtlety is knowing when to stop: it keeps going until no still-unexplored pair of frontier cells could possibly form a shorter route. On an unweighted grid it returns exactly the same length as plain BFS.

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Grow one BFS frontier from the start and another from the goal.
  2. Always expand whichever frontier is currently shallower.
  3. When a cell is reached by both waves, remember that meeting as a candidate path.
  4. Stop once no shorter meeting is possible, then join the two halves.

Pseudocode

1bidirectional(grid, start, goal):    # O(b^(d/2))2  BFS forward from start AND backward from goal3  expand whichever frontier is shallower4  when a cell is reached by both sides:5    record start→…→cell→…→goal as a candidate6  stop once no shorter meeting can exist7  stitch the two halves at the meeting cell