import heapq

Dijkstra's algorithm to find shortest paths from a source node

def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 queue = [(0, start)] while queue: current_dist, current_node = heapq.heappop(queue) if current_dist > distances[current_node]: continue for neighbor, weight in graph[current_node]: distance = current_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(queue, (distance, neighbor)) return distances

Example graph as adjacency list

graph = { 'A': [('B', 1), ('C', 4)], 'B': [('A', 1), ('C', 2), ('D', 5)], 'C': [('A', 4), ('B', 2), ('D', 1)], 'D': [('B', 5), ('C', 1)] }

Find shortest paths from 'A'

shortest_paths = dijkstra(graph, 'A') print("Shortest distances from A:") for node, dist in shortest_paths.items(): print(f"A -> {node}: {dist}")