ダイクストラ法

2022年7月18日

問題

頂点数が $\small N$、辺の数が $\small M$ のグラフでそれぞれの辺の重みが $\small W (\ge 0)$ であるとき、ある頂点から各頂点までの最短経路を求める。

計算量

$ O((N+M)\log M) $。

コード例（Python）

def dijkstra(u, graph):
    heap = []
    n = len(graph)
    visited = [False for _ in range(n)]
    dist = [INFTY for _ in range(n)]
    dist[u] = 0
    heappush(heap, (dist[u], u))
    while len(heap) > 0:
        wu, u = heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v, wv in graph[u]:
            if not visited[v] and dist[v] > wu + wv:
                dist[v] = wu + wv
                heappush(heap, (dist[v], v))
    return dist