Home/Pathfinding/Bidirectional BFS
Search algorithmsCTRL K

Bidirectional BFS

· two frontiers that meet in the middle
/pathfinding/bidirectional-bfs
EXPANDED
0
closed cells
FROM START
1
cells reached that side
FROM GOAL
1
cells reached that side
RINGS
0
one per turn, alternating
PATH
—
length once the goal is reached
closedboth frontiersmeeting cellpathstart / goal
44×20 · 28% walls · seed 7 · two frontiers · 89 steps
step 0 / 88
Walls28
bidirectional_bfs.ts
1
function bidirectionalBfs(grid: Grid, start: Cell, goal: Cell) {
2
  const front = { ring: [start], parent: new Map([[start, null]]) }, back = { ring: [goal], parent: new Map([[goal, null]]) };
3
  while (front.ring.length > 0 && back.ring.length > 0) {
4
    const meeting = expand(grid, front, back); // one ring from the start side
5
    if (meeting) return join(front.parent, back.parent, meeting);
6
    const met = expand(grid, back, front); // one ring from the goal side
7
    if (met) return join(front.parent, back.parent, met);
8
  }
9
  return null;
10
}
11
function expand(grid: Grid, side: Side, other: Side) {
12
  for (const current of side.ring.splice(0)) {
13
    for (const neighbor of neighbors(grid, current)) {
14
      if (side.parent.has(neighbor)) continue;
15
      side.parent.set(neighbor, current); side.ring.push(neighbor);
16
      if (other.parent.has(neighbor)) return neighbor;
17
    }
18
  }
19
  return null;
20
}
CURRENT STEP
line 2

Two searches: one from the start (12, 1), one from the goal (5, 42). They take turns growing one ring each.

// how it works

Understanding Bidirectional BFS

bidirectional BFS · two small circles instead of one big one
01

The idea

Bidirectional search runs two breadth-first searches at once, one from the start and one from the goal, growing one ring each in turn. The moment a cell is reached by both, the two parent chains join through it and form a shortest path.

The saving comes from geometry. A single BFS to distance d fills a disc of about d² cells; two searches to distance d/2 fill two discs of (d/2)² each, half the area in total. On graphs with high branching the saving is exponential: b^(d/2) instead of b^d.

02

The four stages

1
start ringone BFS layer from the start side
2
goal ringone BFS layer from the goal side
3
meeta cell reached from both sides
4
jointhe two parent chains through it
03

Complexity

best
O(d)start and goal adjacent
average
O(b^(d/2))two half-depth searches
worst
O(V + E)no path: both sides flood
space
O(b^(d/2))two frontiers, two parent maps
04

Versus its siblings

CELLS EXPANDED · 44×20 MAZE
bfs
612
dijkstra
604
bidirectional
310
a*
188
greedy
96
jps
41
same maze, same start and goal
05

Pseudocode

BIDIRECTIONALBFS(start, goal)
  front ← BFS state from start; back ← BFS state from goal
  repeat
    grow front by one ring; if it touches a cell back has reached: join the two parent chains there
    grow back by one ring; same check
  until either side has no ring left: no path
06

When to use

Unweighted shortest paths between two known points: word ladders, social 'degrees of separation', puzzle states.
Whenever both endpoints are known and the graph is large; on a map it halves BFS's work, on a state space it squares-roots it.
07

Pitfalls

Stopping at the first meeting is only correct when the sides alternate ring by ring; expanding one side ahead can miss a shorter join.
Directed graphs need the backward search to follow edges in reverse.
With weights, use bidirectional Dijkstra and a careful stopping rule; the first meeting is not the shortest path.
08

History

Ira Pohl analysed bidirectional search in his 1969 thesis and 1971 paper, and it has been standard in route planning ever since: contraction hierarchies and hub labels, the engines behind today's map services, run a bidirectional Dijkstra at their core.

Back to Pathfinding