dijkstra

dijkstra.py

# graph: node -> [(neighbor_1, weight_1), (neighbor_2, weight_2), ...]
import heapq

def dijkstra(graph, start):
    pq = [(0, start)]
    
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    prev = {node: None for node in graph}
    
    while pq:
        current_dist, current_node = heapq.heappop(pq)
        
        if current_dist > dist[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            new_dist = current_dist + weight
            
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = current_node
                heapq.heappush(pq, (new_dist, neighbor))
    
    return dist, prev