breadthfirst search shortest path implementations doctest python m doctest v bfsshortestpath py manual test python bfsshortestpath py find shortest path between start and goal nodes args graph dict nodelist of neighboring nodes keyvalue pairs start start node goal target node returns shortest path between start and goal nodes as a string of nodes not found string if no path found example bfsshortestpathdemograph g d g c a b d bfsshortestpathdemograph g g g bfsshortestpathdemograph g unknown keep track of explored nodes keep track of all the paths to be checked return path if start is goal keeps looping until all possible paths have been checked pop the first path from the queue get the last node from the path go through all neighbour nodes construct a new path and push it into the queue return path if neighbour is goal mark node as explored in case there s no path between the 2 nodes find shortest path distance between start and target nodes args graph nodelist of neighboring nodes keyvalue pairs start node to start search from target node to search for returns number of edges in shortest path between start and target nodes 1 if no path exists example bfsshortestpathdistancedemograph g d 4 bfsshortestpathdistancedemograph a a 0 bfsshortestpathdistancedemograph a unknown 1 keep tab on distances from start node find shortest path between start and goal nodes args graph dict node list of neighboring nodes key value pairs start start node goal target node returns shortest path between start and goal nodes as a string of nodes not found string if no path found example bfs_shortest_path demo_graph g d g c a b d bfs_shortest_path demo_graph g g g bfs_shortest_path demo_graph g unknown keep track of explored nodes keep track of all the paths to be checked return path if start is goal keeps looping until all possible paths have been checked pop the first path from the queue get the last node from the path go through all neighbour nodes construct a new path and push it into the queue return path if neighbour is goal mark node as explored in case there s no path between the 2 nodes find shortest path distance between start and target nodes args graph node list of neighboring nodes key value pairs start node to start search from target node to search for returns number of edges in shortest path between start and target nodes 1 if no path exists example bfs_shortest_path_distance demo_graph g d 4 bfs_shortest_path_distance demo_graph a a 0 bfs_shortest_path_distance demo_graph a unknown 1 keep tab on distances from start node returns g c a b d returns 4
demo_graph = {
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}


def bfs_shortest_path(graph: dict, start, goal) -> list[str]:
    
    
    explored = set()
    
    queue = [[start]]

    
    if start == goal:
        return [start]

    
    while queue:
        
        path = queue.pop(0)
        
        node = path[-1]
        if node not in explored:
            neighbours = graph[node]
            
            
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                
                if neighbour == goal:
                    return new_path

            
            explored.add(node)

    
    return []


def bfs_shortest_path_distance(graph: dict, start, target) -> int:
    
    if not graph or start not in graph or target not in graph:
        return -1
    if start == target:
        return 0
    queue = [start]
    visited = set(start)
    
    dist = {start: 0, target: -1}
    while queue:
        node = queue.pop(0)
        if node == target:
            dist[target] = (
                dist[node] if dist[target] == -1 else min(dist[target], dist[node])
            )
        for adjacent in graph[node]:
            if adjacent not in visited:
                visited.add(adjacent)
                queue.append(adjacent)
                dist[adjacent] = dist[node] + 1
    return dist[target]


if __name__ == "__main__":
    print(bfs_shortest_path(demo_graph, "G", "D"))  
    print(bfs_shortest_path_distance(demo_graph, "G", "D"))