__init__ (11).py

import heapq

def dijkstra(graph, start_node):
    """
    Finds the shortest path from a start node to all other nodes in a weighted graph.
    
    Args:
        graph (dict): A dictionary representing the graph. 
                      Format: {node: [(neighbor, weight), ...]}
        start_node (str): The node to start the search from.
        
    Returns:
        dict: A dictionary of the shortest distance from the start node to every other node.
    """
    
    # Initialize distances: 0 for start, infinity for all others
    # This is where the magic begins—we optimistically assume the cost is infinite
    # until we find a path.
    distances = {node: float('infinity') for node in graph}
    distances[start_node] = 0
    
    # Priority queue stores tuples of (distance, node)
    # The smallest distance is always at the top (pop)
    priority_queue = [(0, start_node)]

    # The main loop continues as long as there are nodes to process
    while priority_queue:
        # Get the node with the smallest current distance
        current_distance, current_node = heapq.heappop(priority_queue)

        # Ignore paths that are already longer than the known shortest path
        if current_distance > distances[current_node]:
            continue

        # Explore the neighbors of the current node
        for neighbor, weight in graph.get(current_node, []):
            
            # Calculate the distance to the neighbor through the current path
            new_distance = current_distance + weight

            # If the new path is shorter, update the distance and push to the queue
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(priority_queue, (new_distance, neighbor))

    return distances

# --- Example Usage ---

# Define the graph:
# Format: {Node: [(Neighbor, Weight), ...]}
# Think of this as a set of roads (edges) with travel times (weights).
# 
graph_map = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': [('E', 3)],
    'E': [('F', 2)],
    'F': [('A', 5), ('G', 1)], # A loop back to 'A'
    'G': [('E', 1)]
}

start = 'A'
shortest_distances = dijkstra(graph_map, start)

print(f"Starting Node: {start}\n")
print("Shortest Distances to All Nodes:")
print("---------------------------------")
for node, distance in shortest_distances.items():
    if distance != float('infinity'):
        print(f"Path to {node}: {distance}")
    else:
        print(f"Path to {node}: No path exists")

# Expected Output:
# A -> A: 0
# A -> B: 1
# A -> C: 3 (via B: 1 + 2)
# A -> D: 4 (via B -> C: 1 + 2 + 1)
# A -> E: 7 (via D: 4 + 3)
# A -> F: 9 (via E: 7 + 2)
# A -> G: 10 (via F: 9 + 1)