Template: 16. DIJKSTRA — Shortest Path (Weighted Graph)

16. DIJKSTRA — Shortest Path (Weighted Graph)

# =============================================================================
import heapq

def dijkstra(graph, start, n):
    """graph: adjacency list {node: [(neighbor, weight), ...]}"""
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist


# =============================================================================