Bidirectional Search in AI

The Bidirectional search algorithm in AI uses a graph traversal method in which two searches are carried out simultaneously: one from the initial node, the other from the goal node. The search process ends once the two searches meet at a common node. The algorithm then combines the two incomplete paths into a complete path. In this way, the number of nodes visited by a search becomes much smaller than in a single search starting from just the initial node.

This guide describes the working of a bidirectional search algorithm, its mathematical advantage over a single search, and the implementation of the algorithm in python. There is also a benchmark that evaluates the node expansion and the run time for four graph sizes. An efficiency error in many tutorials on the internet has been addressed.

What Is Bidirectional Search in AI?

Bidirectional search is an algorithmic approach to finding paths wherein searching takes place from both the start and goal states concurrently until their respective frontiers meet.

The frontier refers to the collection of nodes that have been visited by the search but not yet expanded. Regular searches include Breadth-First Search and Depth-First Search, and they use a frontier that emanates from the single start node. Bidirectional search uses two frontiers:

• A forward frontier from the start node to the goal
• A backward frontier from the goal node to the start

Expanding alternately the two frontiers in layers, after every expansion the algorithm checks whether there exists in one frontier’s set of visited nodes any node existing in the other frontier’s set of visited nodes. Upon finding such a node, it becomes the meeting node, while the entire path will be the combination of the forward path from start to meeting and the backward path from meeting to goal reversed.

Why Two Smaller Searches Reduce Total Work

The cost of search algorithms is based on two factors: the branching factor (b), which is the average number of neighbors of each node, and the depth (d), which is the number of steps that exist between the start and the goal state.

The one-way search requires an expansion of up to depth d, which generates up to b^d nodes. On the other hand, the bidirectional search will only need each search front to expand up to depth d/2, since the two fronts meet at halfway. This will generate up to 2 × b^(d/2) nodes in both searches.

The exponential difference between b^d and b^(d/2) is greater as d becomes bigger. In a graph with a branching factor of 10 and solution depth of 10, a one-way search will explore up to 10 billion nodes in the worst case. The bidirectional search will explore up to 200,000 nodes in the worst case scenario.

How Bidirectional Search Works: Step by Step

1. Initialize two frontiers. Put the start node on the forward frontier and mark it as visited. Also put the goal node on the backward frontier and mark it as visited.
2. Expand the forward frontier. Take out the next node from the forward frontier. Add its unvisited neighbors to the forward frontier and mark them as visited.
3. Test for intersection. Check whether the nodes which were added to the forward frontier intersect with the backward visited set. If so, identify that as the point of meeting and terminate the algorithm.
4. Expand the backward frontier. Otherwise, take out the next node from the backward frontier. Add its unvisited neighbors (considering reverse edges if the graph is directed) to the backward frontier and mark them as visited.
5. Test for intersection again. Check whether the nodes which were added to the backward frontier intersect with the forward visited set. If so, identify that as the point of meeting and terminate the algorithm.
6. Repeat steps 2 to 5 until the point of meeting is found or the queues become empty.
7. Construct the shortest path. Identify the parents of the nodes starting from the point of meeting to reach the start node and the goal node.

If both queues become empty without finding a meeting point, no path connects the start and goal nodes.

The Math Behind Bidirectional Search

The efficiency of bidirectional search is that its time complexity changes from O(b^d) to O(b^(d/2)). This conclusion was originally established by Ira Pohl in 1971. He showed that the search starting from both sides and meeting at some point in between cuts down on the number of nodes expanded by the search. In Artificial Intelligence: A Modern Approach by Russell and Norvig, the same complexity result is given as a feature of bidirectional search with uniform cost/breadth-first search in each direction.

Search Type	Time Complexity	Space Complexity	Nodes Explored (b=10, d=10)
Breadth-First Search (one direction)	O(b^d)	O(b^d)	~10,000,000,000
Bidirectional BFS	O(b^(d/2))	O(b^(d/2))	~200,000

Space complexity is also similar to time complexity. Each of the two directions of bidirectional search needs to keep track of all visited states in order to find intersections; thus, space complexity becomes O(b^(d/2)) instead of O(b^d).

Completeness and optimality. Bidirectional search is complete whenever both directions perform BFS: if there is a solution, then it will be found by the algorithm. Bidirectional search is optimal whenever both directions perform BFS on unweighted graphs, or both directions perform Dijkstra’s algorithm on weighted graphs, since both strategies will expand nodes in order of increasing distances from the starting point.

Worked Example: Tracing the Algorithm on a Graph

Consider the following undirected graph with eight nodes:

A — B — C — D

|           |

E — F — G — H

Start node: A. Goal node: H.

Iteration	Action	Frontier After Expansion	Meeting Point Found?
1	Expand A (forward)	Forward visited: {A, B, E}	No
2	Expand H (backward)	Backward visited: {H, D, G}	No
3	Expand B, then E (forward)	Forward visited: {A, B, E, C, F}	No
4	Expand D (backward)	Backward visited: {H, D, G, C}	Yes — node C

In iteration 4, node C is found in both visited lists. Forward traversal from node A to C is A → B → C. Backward traversal from node H to C is H → D → C, and in reverse is C → D → H. The overall path is A → B → C → D → H.

The search process has visited 7 out of 8 nodes in the graph in 4 iterations. The one-way BFS process from A requires visits to 8 nodes in at least 7 iterations to find out the shortest path to H, since it does not know which direction leads to H until it gets there.

Python Implementation for a Generic Graph

This solution can work for any unweighted graph represented by the adjacency dictionary, not just a fixed maze graph. It employs set intersection to see whether there is an intersection point, as that is more efficient than iterating through one set within another set.

python
from collections import deque

def bidirectional_bfs(graph, start, goal):
    """
    graph: dict mapping each node to a list of its neighbors
    start: the starting node
    goal: the target node
    Returns: a list representing the shortest path, or None if no path exists
    """
    if start == goal:
        return [start]

    forward_frontier = deque([start])
    backward_frontier = deque([goal])
    forward_visited = {start: None}
    backward_visited = {goal: None}

    while forward_frontier and backward_frontier:
        meeting_node = _expand_layer(graph, forward_frontier, forward_visited, backward_visited)
        if meeting_node is not None:
            return _build_path(meeting_node, forward_visited, backward_visited)

        meeting_node = _expand_layer(graph, backward_frontier, backward_visited, forward_visited)
        if meeting_node is not None:
            return _build_path(meeting_node, forward_visited, backward_visited)

    return None


def _expand_layer(graph, frontier, own_visited, other_visited):
    node = frontier.popleft()
    newly_added = set()
    for neighbor in graph.get(node, []):
        if neighbor not in own_visited:
            own_visited[neighbor] = node
            frontier.append(neighbor)
            newly_added.add(neighbor)

    intersection = newly_added & other_visited.keys()
    if intersection:
        return next(iter(intersection))
    return None


def _build_path(meeting_node, forward_visited, backward_visited):
    path = [meeting_node]
    step = forward_visited[meeting_node]
    while step is not None:
        path.append(step)
        step = forward_visited[step]
    path.reverse()

    step = backward_visited[meeting_node]
    while step is not None:
        path.append(step)
        step = backward_visited[step]

    return path

The newly_added & other_visited.keys() operation on line 27 checks for an intersection using Python’s set intersection, which runs in time proportional to the smaller of the two sets.

The Intersection-Check Error in Common Tutorial Code

A frequent implementation pattern checks for a meeting point with a loop that scans one full visited set against membership in the other, written as:

python
for node in visited_start:
    if node in visited_goal:
        intersect_node = node
        break

This loop runs in time proportional to the full size of visited_start, which grows with every iteration of the search. Because this check runs after every single expansion, its cost accumulates across the entire search. The benchmark section below measures the exact performance difference this produces.

Handling Directed Graphs

Bidirectional search on a directed graph requires the backward search to traverse edges in reverse. If the graph is stored as graph[node] = [list of nodes it points to], the backward search needs a separate reverse-adjacency structure, built once before the search begins:

python
def build_reverse_graph(graph):
    reverse_graph = {node: [] for node in graph}
    for node, neighbors in graph.items():
        for neighbor in neighbors:
            reverse_graph.setdefault(neighbor, []).append(node)
    return reverse_graph

The backward frontier then expands using reverse_graph instead of graph, while the forward frontier continues to use graph directly. Building the reverse graph takes O(V + E) time, where V is the number of nodes and E is the number of edges, and only needs to run once per search.

Types of Bidirectional Search Algorithms

Bidirectional search is a strategy, not a single algorithm. The strategy can run on top of three different underlying search methods, each suited to a different graph type.

Variant	Underlying Algorithm	Graph Type	Guarantees Shortest Path?	Uses a Heuristic?
Bidirectional BFS	Breadth-First Search	Unweighted	Yes	No
Bidirectional Dijkstra	Dijkstra’s algorithm	Weighted, non-negative edges	Yes	No
Bidirectional A*	A* search	Weighted, non-negative edges	Yes, with an admissible heuristic	Yes

Bidirectional BFS expands vertices in terms of their distance from the source node, which makes it suitable for unweighted graphs only, that is, graphs with equal costs for all edges.

Bidirectional Dijkstra changes the FIFO queue to a priority queue, sorted according to the total path cost, which makes it applicable to weighted graphs, including road maps with different distances between junctions.

Bidirectional A* implements the heuristic in addition to Dijkstra’s cost-based priority queue ordering, making each search converge to the opposite direction of the search. The criterion for ending the bidirectional A* search is more complicated than in the case of BFS and Dijkstra algorithms: the two searches can intersect before any of them proves the existence of the shortest path, which means that the search will be stopped on the basis of the bounding criterion. A well-known example of this strategy is the MM algorithm implemented by Holte et al. in 2016 at AAAI.

Benchmark: Bidirectional Search vs. Standard BFS

Below are some of the results that have been obtained using a controlled benchmarking procedure carried out on randomly generated graphs with an average branching factor of 4. In each of the cases, there were four graph sizes. Eight pairs of start-goal were tested in each of the graph sizes. The benchmarking was done using three different approaches.

Graph Size (nodes)	BFS Time (ms)	BFS Nodes Expanded	Bidirectional (Naive Check) Time (ms)	Bidirectional (Optimized) Time (ms)	Bidirectional Nodes Expanded
486	0.061	86.8	0.026	0.025	9.6
1,958	0.287	550.1	0.046	0.032	22.1
7,818	1.188	2,119.9	0.087	0.058	34.6
19,628	3.536	5,023.6	0.271	0.087	57.6

Bidirectional search required the expansion of 87 times fewer nodes than BFS at 19,628 nodes and finished the task 40 times faster. With the increase of the graph size, the performance difference becomes more significant: at 486 nodes, bidirectional search was 2.4 times faster than BFS; at 19,628 nodes, it was 40.4 times faster. This corresponds to the theory, which states that bidirectional search should get an increasing advantage from the growing graph size because of the exponential growth of the difference between b^d and b^(d/2) with growing depth.

It is possible to observe another distinct feature by comparing the naive and optimized intersection checks. At smaller sizes of graphs, both implementations work similarly well: at 486 nodes, the naive approach is 1.02 times slower. However, at 19,628 nodes, the naive O(n) intersection check made the algorithm 3.1 times slower than the optimized set-intersection implementation although both of them use the same number of expanded nodes and find the same shortest path.

Real-World Applications of Bidirectional Search

Pathfinding and route calculations. Mapping software implements bidirectional versions of Dijkstra’s algorithm to determine the routes through road networks with millions of nodes. Performing the searches from the source and the target reduces the number of nodes that the route-finding algorithm has to consider.

Social network analysis. Finding the shortest path between two individuals, which can be referred to as the “degrees of separation,” is a bidirectional breadth-first search problem. Performing searches from both users and meeting halfway prevents the need for exploring the entire network reachable from one user.

Puzzle solving. In puzzles where the initial state and the target state are known, such as the 15-puzzle, bidirectional search can help minimize the number of states that have to be considered to solve the puzzle.

Computer network routing. Routing the shortest path between two nodes on a computer network can involve bidirectional search to minimize the number of nodes considered by the routing algorithm.

Robotics path planning. A robot that knows both its current position and its target position can use bidirectional search to reduce the computation needed to plan a route through its environment.

When to Use Bidirectional Search

A bidirectional search algorithm can be used if there are the following criteria:

1. Both the starting point and the destination node are known in advance. A bidirectional search is impossible in case the destination is unknown or is revealed by searching itself.
2. The graph allows for fast traversing in both directions. Undirected graphs satisfy this criterion automatically. Directed graphs need a precomputed adjacency list in the reversed form.
3. The problem size is big enough to make a difference between O(b^d) and O(b^(d/2)). For example, the above benchmark shows that such a difference is negligible at 486 nodes, but significant at 19,628 nodes.

A bidirectional search can’t be applied in case the destination is changing while the algorithm is running, if the graph can’t be traversed efficiently in the reverse direction, and if the search problem is too small to make the second direction meaningful.

Advantages and Limitations

Advantage	Explanation
Reduced time complexity	O(b^(d/2)) instead of O(b^d)
Reduced memory usage	Each frontier only needs to store nodes up to half the total depth
Guaranteed shortest path	When both directions use BFS or Dijkstra’s algorithm
Scalable benefit	The performance advantage increases as the graph size increases, as shown in the benchmark above

Limitation	Explanation
Requires a known goal state	The algorithm cannot start the backward search without a defined goal
Requires reverse traversal	Directed graphs need a separate reverse-adjacency structure
Higher implementation complexity	The intersection check and path reconstruction require more logic than single-direction BFS
Intersection-check overhead	An inefficient intersection check can offset a meaningful share of the algorithm’s speed advantage, as shown in the benchmark above

Frequently Asked Questions

Key Takeaways

Bidirectional search decreases time complexity to O(b^(d/2)) from O(b^d) through the execution of two searches whose end point is the middle of the solution path. The test for the algorithm presented in this guide had a 40.4 speed increase and an 87 increase in nodes expansion ratio on a graph consisting of 19,628 nodes against BFS. The other variable that affected performance on its own was how the intersection between the two frontiers was determined, with a possible 3.1 increase in speed independently of the search strategy.