Dijkstra's Algorithm

def dijkstra(graph, start):
    # Priority queue to store (distance, vertex)
    pq = []
    heapq.heappush(pq, (0, start))  # Push the start vertex with distance 0
    
    # Dictionary to store shortest distances
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0

    # Set to track visited nodes
    visited = set()

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

        if current_vertex in visited:
            continue

        visited.add(current_vertex)

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

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

    return distances