Dijkstra’s Algorithm

Dijkstra’s algorithm is a shortest path algorithm that finds the shortest path between a source vertex and all other vertices in a weighted graph with non-negative weights. It uses a priority queue to maintain a set of unvisited vertices with the minimum distance from the source vertex, and iteratively selects the vertex with the smallest distance, updates its neighbors’ distances, and marks the vertex as visited.

Here’s the Python code for Dijkstra’s algorithm:

import heapq

def dijkstra(graph, start):
    distances = {v: float('inf') for v in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        curr_dist, curr_node = heapq.heappop(pq)
        
        if curr_dist > distances[curr_node]:
            continue
        
        for neighbor, weight in graph[curr_node].items():
            distance = curr_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

This code takes a graph represented as a dictionary of dictionaries, where the keys of the outer dictionary are the vertices of the graph, and the values are dictionaries that map the neighbors of the vertex to the corresponding edge weights. The start vertex is also provided as an argument.

The function initializes a dictionary of distances with all values set to infinity, except for the start vertex, which is set to 0. It also initializes a priority queue with a tuple containing the current distance and the current node. The algorithm iteratively selects the vertex with the smallest distance from the priority queue, updates the distances of its neighbors if a shorter path is found, and marks the vertex as visited. Finally, the function returns the distances dictionary, which contains the shortest distances from the start vertex to all other vertices in the graph.