Function bidirectional_search

graphs/bidirectional_search.py:49–148

Perform bidirectional search on a graph to find the shortest path. Args: graph: A dictionary where keys are nodes and values are lists of adjacent nodes start: The starting node goal: The target node Returns: A list representing the path from start to g

(
    graph: dict[int, list[int]], start: int, goal: int
)

def bidirectional_search(
    graph: dict[int, list[int]], start: int, goal: int
) -> list[int] | None:
    """
    Perform bidirectional search on a graph to find the shortest path.

    Args:
        graph: A dictionary where keys are nodes and values are lists of adjacent nodes
        start: The starting node
        goal: The target node

    Returns:
        A list representing the path from start to goal, or None if no path exists

    Examples:
        >>> graph = {
        ...     0: [1, 2],
        ...     1: [0, 3, 4],
        ...     2: [0, 5, 6],
        ...     3: [1, 7],
        ...     4: [1, 8],
        ...     5: [2, 9],
        ...     6: [2, 10],
        ...     7: [3, 11],
        ...     8: [4, 11],
        ...     9: [5, 11],
        ...     10: [6, 11],
        ...     11: [7, 8, 9, 10],
        ... }
        >>> bidirectional_search(graph=graph, start=0, goal=11)
        [0, 1, 3, 7, 11]
        >>> bidirectional_search(graph=graph, start=5, goal=5)
        [5]
        >>> disconnected_graph = {
        ...     0: [1, 2],
        ...     1: [0],
        ...     2: [0],
        ...     3: [4],
        ...     4: [3],
        ... }
        >>> bidirectional_search(graph=disconnected_graph, start=0, goal=3) is None
        True
    """
    if start == goal:
        return [start]

    # Check if start and goal are in the graph
    if start not in graph or goal not in graph:
        return None

    # Initialize forward and backward search dictionaries
    # Each maps a node to its parent in the search
    forward_parents: dict[int, int | None] = {start: None}
    backward_parents: dict[int, int | None] = {goal: None}

    # Initialize forward and backward search queues
    forward_queue = deque([start])
    backward_queue = deque([goal])