BFS Shortest Path Template - cocoder39/coco39_LC GitHub Wiki

BFS is specifically useful for finding the shortest path in unweighted graphs where all edges have the same weight (implicitly 1)

• Time Complexity: 𝑂(𝑉+𝐸) where 𝑉 is the number of vertices and E is the number of edges. This is because each node and each edge is processed once.
• Space Complexity: 𝑂(𝑉) , as it uses additional space for the queue, distance, and predecessor tracking.

Option 1: first discovered path to a node is always the shortest. This is guaranteed by the nature of BFS in unweighted graphs.

from collections import deque

def bfs_shortest_path_infinity_check(graph, start, target):
    queue = deque([start])
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}

    while queue:
        current = queue.popleft()

        for neighbor in graph[current]:
            if distances[neighbor] == float('inf'):  # Only check if distance is infinity
                distances[neighbor] = distances[current] + 1
                predecessors[neighbor] = current
                queue.append(neighbor)

    # Reconstruct path
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors[current]
    path.reverse()

    return path if distances[target] != float('inf') else None

# Example usage:
print(bfs_shortest_path_infinity_check(graph, 'A', 'F'))  # Expected output: ['A', 'C', 'D', 'F']

Option 2: a more general way to get shortest path is to update only if a shorter path is found.

from collections import deque

def bfs_shortest_path(graph, start, target):
    queue = deque([start])
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}

    while queue:
        current = queue.popleft()

        for neighbor in graph[current]:
            new_distance = distances[current] + 1
            if new_distance < distances[neighbor]:  # Update if a shorter path is found
                distances[neighbor] = new_distance
                predecessors[neighbor] = current
                queue.append(neighbor)

    # Reconstruct path
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors[current]
    path.reverse()

    return path if distances[target] != float('inf') else None

# Example usage:
print(bfs_shortest_path(graph, 'A', 'F'))  # Expected output: ['A', 'C', 'D', 'F']