Dijkstra’s algorithm in Python

Dijkstra’s algorithm:

1. Importing Required Modules:

import heapq

The code imports the heapq module, which provides  an implementation of the heap queue (priority queue) algorithm.

2. Dijkstra’s Algorithm Implementation:

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

• The dijkstra function takes two parameters: graph (the graph represented as an adjacency dictionary) and start (the starting node for finding shortest paths).
• It initializes a distances dictionary, setting the initial distance to infinity for all nodes except the start node, which is set to 0.
• priority_queue is a list used as a min-heap to keep track of nodes and their distances. Each element in the heap is a tuple containing (distance, node).

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

        if current_distance > distances[current_node]:
            continue

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

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

• The algorithm iterates as long as the priority_queue is not empty.
• It pops the node with the smallest distance from the priority_queue. If the extracted distance is larger than the stored distance for the current node, the loop continues to the next iteration.
• For each neighbor of the current node, the algorithm calculates a tentative distance. If this distance is shorter than the previously stored distance for the neighbor, the distances dictionary is updated, and the neighbor is added to the priority queue for further exploration.

    return distances

5. Example Graph and Output:

graph = {
    'A': {'B': 10, 'C': 5},
    'B': {'A': 10, 'D': 1},
    'C': {'A': 5, 'D': 3},
    'D': {'B': 1, 'C': 3}
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)

print("Shortest distances from node", start_node + ":")
for node, distance in shortest_distances.items():
    print(node + ":", distance)

• The provided graph is represented as an adjacency dictionary.
• The dijkstra function is called with the graph and the start_node (‘A’ in this case).
• The shortest distances from node ‘A’ to all other nodes are calculated and printed.