BFS

from collections import deque

def bfs_shortest_path(graph, start, goal):

    # Initialize a queue with the start node and its path

    queue = deque([(start, [start])])  # Each element is (current_node, path_to_current_node)

    visited = set()  # To keep track of visited nodes

    while queue:

        current_node, path = queue.popleft()  # Dequeue a node and its path

        if current_node == goal:  # If the goal is reached, return the path

            return path

        if current_node not in visited:

            visited.add(current_node)  # Mark the node as visited

            

            # Add all unvisited neighbors to the queue with their respective paths

            for neighbor in graph.get(current_node, []):

                if neighbor not in visited:

                    queue.append((neighbor, path + [neighbor]))

    return None  # Return None if no path is found

# Example graph

graph = {

    'S': ['A', 'B'],

    'A': ['C', 'D'],

    'B': ['G', 'H'],

    'C': ['E', 'F'],

    'D': [],

    'E': ['K'],

    'F': [],

    'G': ['I'],

    'H': [],

    'I': [],

    'K': []

}

# User input for start and goal nodes

start_node = input("Enter the start node: ").strip()

goal_node = input("Enter the goal node: ").strip()

# Validate if the nodes exist in the graph

if start_node not in graph or goal_node not in graph:

    print("Invalid start or goal node. Please ensure the nodes exist in the graph.")

else:

    # Find and display the shortest path

    shortest_path = bfs_shortest_path(graph, start_node, goal_node)

    if shortest_path:

        print("Shortest Path:", " -> ".join(shortest_path))

    else:

        print(f"No path exists between {start_node} and {goal_node}.")