Bidirectional Search Pathfinding

Speed:

SlowFast

Start

End

Wall

Visited from Start

Visited from End

Current from Start

Current from End

Path

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(b^{d / 2}), where b is branching factor, d is shortest path length

Space Complexity: O(b^{d / 2}) for both queues and visited sets

Optimal: Yes for unweighted graphs (finds shortest path)

Complete: Yes (will find solution if one exists)

How it works: Uses two BFS searches—one from start, one from end—until they meet. Traces path from both sides.

Best for: Large, unweighted graphs where start/end are far apart.

Implementation

function bidirectionalBFS(grid, start, end) {
  const queueA = [start], queueB = [end];
  const visitedA = new Set(), visitedB = new Set();
  start.parentA = null; end.parentB = null;
  while (queueA.length && queueB.length) {
    // BFS from start
    let currentA = queueA.shift();
    if (visitedB.has(`${currentA.row},${currentA.col}`))
      return reconstructPath(currentA);
    visitedA.add(`${currentA.row},${currentA.col}`);
    for (const neighbor of getNeighbors(currentA)) {
      if (!visitedA.has(`${neighbor.row},${neighbor.col}`) && neighbor.type !== "wall") {
        neighbor.parentA = currentA;
        queueA.push(neighbor);
      }
    }
    // BFS from end
    let currentB = queueB.shift();
    if (visitedA.has(`${currentB.row},${currentB.col}`))
      return reconstructPath(currentB);
    visitedB.add(`${currentB.row},${currentB.col}`);
    for (const neighbor of getNeighbors(currentB)) {
      if (!visitedB.has(`${neighbor.row},${neighbor.col}`) && neighbor.type !== "wall") {
        neighbor.parentB = currentB;
        queueB.push(neighbor);
      }
    }
  }
  return null;
}