Bidirectional Search Algorithm — BFS from Both Ends

Google Maps finds the shortest route between any two points on Earth in milliseconds. Standard Dijkstra from source to destination on a graph with 100 million nodes would be far too slow. Bidirectional Dijkstra (bidirectional search with weights) is one of the key techniques that makes this practical — along with A* and contraction hierarchies.

The exponential improvement from O(b^d) to O(b^(d/2)) is real and dramatic. For a typical road network with branching factor b=4 and depth d=20, standard search explores 4^20 ≈ 10^12 nodes. Bidirectional explores 2×4^10 ≈ 2×10^6 nodes. A factor of 500,000 difference.

Why Bidirectional Search is Faster

Standard BFS explores all nodes up to depth d: O(b + b² + ... + b^d) ≈ O(b^d)

Bidirectional BFS: each direction explores to depth d/2: O(2 × b^(d/2)) ≈ O(b^(d/2))

For b=10, d=10: - Standard: 10^10 = 10 billion nodes - Bidirectional: 2 × 10^5 = 200,000 nodes

A reduction by factor ~50,000.

Implementation

from collections import deque

def bidirectional_bfs(graph: dict, start, end) -> int:
    """Returns shortest path length, -1 if not found."""
    if start == end: return 0
    # Forward and backward frontiers + visited sets
    front_visited = {start: 0}
    back_visited  = {end: 0}
    front_queue = deque([start])
    back_queue  = deque([end])

    def expand(queue, visited, other_visited):
        node = queue.popleft()
        for neighbour in graph.get(node, []):
            if neighbour not in visited:
                visited[neighbour] = visited[node] + 1
                queue.append(neighbour)
                if neighbour in other_visited:
                    return visited[neighbour] + other_visited[neighbour]
        return None

    while front_queue and back_queue:
        result = expand(front_queue, front_visited, back_visited)
        if result is not None: return result
        result = expand(back_queue, back_visited, front_visited)
        if result is not None: return result
    return -1

graph = {
    'A': ['B','C'], 'B': ['A','D','E'],
    'C': ['A','F'], 'D': ['B'],
    'E': ['B','F'], 'F': ['C','E','G'],
    'G': ['F']
}
print(bidirectional_bfs(graph, 'A', 'G'))  # 3

Applications

Google Maps / GPS: Route planning between two known locations — bidirectional Dijkstra instead of BFS for weighted graphs.

Word Ladder: Find shortest transformation sequence — bidirectional BFS from both start and end words.

Social networks: Shortest path between two users — bidirectional BFS from both users' friend lists.

Chess / game AI: Bidirectional iterative deepening for known goal states.

Complexity

Time: O(b^(d/2)) where b=branching factor, d=shortest path depth Space: O(b^(d/2)) for both frontiers

The meeting condition must be handled carefully — the first meeting point may not give the shortest path. The correct termination is when the sum of forward and backward distances through any meeting node is minimised.

Frequently Asked Questions