Dijkstra

 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
40
41

import heapq

def dijkstra(graph, start):
    # Create a priority queue
    priority_queue = []
    # Initialize the distances with infinity
    distances = {vertex: float('infinity') for vertex in graph}
    # Distance to the start node is zero
    distances[start] = 0
    # Push the start node to the priority queue
    heapq.heappush(priority_queue, (0, start))

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Nodes can be added multiple times to the priority queue, we only process nodes with the smallest distance
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Only consider this new path if it's better
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Example graph as an 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}
}

# Running the algorithm
start_node = 'A'
distances = dijkstra(graph, start_node)
print("Shortest distances from node A:", distances)