Discovering the Power of Bidirectional BFS: A More Efficient Pathfinding Algorithm

Introduction

Pathfinding algorithms are incredibly famous because without them we would still be using paper maps to get around and that would be horrible (at least for me). They address the problem of finding a path from a source to a destination avoiding obstacles and minimizing the costs (time, distance, risks, fuel, price, etc.).

There are many algorithms out there to help us get from point A to point B. Some of the most common include A*, Dijkstra’s, Breadth First Search (BFS), and Depth First Search (DFS). The one thing that all of these pathfinding algorithms have in common is that they are all unidirectional, meaning they search in one direction, starting at the source node and ending at the destination node.

But what if we start the search from both directions simultaneously? That’s where Bidirectional Breadth First Search comes into play. Let’s learn more.

Bidirectional Breadth First Search

Simply put, Bidirectional BFS is a graph traversal algorithm that searches for the shortest path between two nodes by performing two BFSs simultaneously, one from the start node and one from the end node. The algorithm terminates when the two BFSs meet at some node in the middle.

But if you’re anything like me, you prefer a visual.

Visualizing Bidirectional BFS

Let’s try to understand how Bidirectional BFS works through the following example.

The start node is 9 and the end node is 2
Goal: To find the shortest path from 9 to 2 using Bidirectional BFS

Step 1: Start moving forward from the start node (green) and backwards from the end node (orange)

Step 2: Just like BFS, at every point, explore the current node’s neighbors until you find the intersecting node

Step 3: Stop once you find an intersecting node

Step 4: Trace back to find the shortest path

Why is This Important?

As we’ve just walked through, you can see that this is actually faster than a traditional BFS.

Bidirectional BFS requires fewer iterations and fewer nodes visited. As you can imagine, this would be incredibly useful when the size of the graph is very large and the cost of traveling in both directions is the same. Additionally, like the A* algorithm, bidirectional search can be guided by a heuristic estimate of remaining distance from start node to end node and vice versa for finding the shortest path possible.

Let’s now look at the implementation and complexity.

Implementation

Below is a simple implementation of Bidirectional BFS in javascript.

const bidirectionalBFS = (startNode, endNode) => {
  // Initialize the start and end nodes and their queues
  let queueStart = [startNode];
  let queueEnd = [endNode];
  let visitedStart = new Set();
  let visitedEnd = new Set();
  visitedStart.add(startNode);
  visitedEnd.add(endNode);

  // Loop until both queues are empty
  while (queueStart.length > 0 && queueEnd.length > 0) {
    // BFS search from start node
    let currentStart = queueStart.shift();
    for (let neighbor of currentStart.neighbors) {
      if (!visitedStart.has(neighbor)) {
        queueStart.push(neighbor);
        visitedStart.add(neighbor);
      }
      // If the neighbor has been visited by the end BFS, return the path
      if (visitedEnd.has(neighbor)) {
        return 'Path found!';
      }
    }
    // BFS search from end node
    let currentEnd = queueEnd.shift();
    for (let neighbor of currentEnd.neighbors) {
      if (!visitedEnd.has(neighbor)) {
        queueEnd.push(neighbor);
        visitedEnd.add(neighbor);
      }
      // If the neighbor has been visited by the start BFS, return the path
      if (visitedStart.has(neighbor)) {
        return 'Path found!';
      }
    }
  }
  // If no path is found, return no path found
  return 'No path found';
};

Time & Space Complexity

Let’s assume b is the branching factor (the maximum number of neighbors of any node) of the tree, and d is the distance between the start and end node. Traditional BFS complexity is O(b^d). In the case of Bidirectional Search, we run two simultaneous search operations with the complexity of each operation as O(b^(d/2)) which makes the total complexity as O(b^(d/2)+b^(d/2)). This clearly is significantly less than O(b^d).

Conclusion

Hopefully by now, you can see how a more bespoke pathfinding algorithm, like bidirectional BFS, can actually be incredibly efficient.