bfs shortest path

    Our FREE site is mostly funded by the Amazon ads ⇓below⇓.

    Support us by clicking ⇑above⇑ next time you plan to buy a product on Amazon.

    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, start, goal):
        # keep track of explored nodes
        explored = []
        # keep track of all the paths to be checked
        queue = [[start]]
    
        # return path if start is goal
        if start == goal:
            return "That was easy! Start = goal"
    
        # keeps looping until all possible paths have been checked
        while queue:
            # pop the first path from the queue
            path = queue.pop(0)
            # get the last node from the path
            node = path[-1]
            if node not in explored:
                neighbours = graph[node]
                # go through all neighbour nodes, construct a new path and
                # push it into the queue
                for neighbour in neighbours:
                    new_path = list(path)
                    new_path.append(neighbour)
                    queue.append(new_path)
                    # return path if neighbour is goal
                    if neighbour == goal:
                        return new_path
    
                # mark node as explored
                explored.append(node)
    
        # in case there's no path between the 2 nodes
        return "So sorry, but a connecting path doesn't exist :("
    
    
    bfs_shortest_path(graph, "G", "D")  # returns ['G', 'C', 'A', 'B', 'D']