How to implement dijkstra's algorithm in Python?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import heapq

def dijkstra(graph, start):
    # Initialize the distances to all nodes to be infinity
    distances = {node: float('inf') for node in graph}
    # Set the distance to the start node to be zero
    distances[start] = 0
    
    # Initialize an empty priority queue
    pq = []
    # Add the start node to the priority queue
    heapq.heappush(pq, (0, start))
    
    while pq:
        # Extract the node with the smallest distance from the priority queue
        distance, node = heapq.heappop(pq)
        if distance > distances[node]:
            continue
        # Update the distances of the neighbors of the current node
        for neighbor, weight in graph[node].items():
            new_distance = distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(pq, (new_distance, neighbor))
    
    # Return the distances to all nodes
    return distances

# Example usage
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6},
}

print(dijkstra(graph, 'A'))

1

{'A': 0, 'B': 5, 'C': 1, 'D': 2, 'E': 4, 'F': 8}