二分ヒープによるダイクストラ法 (Dijkstra’s Algorithm with Binary Heap)

概要

単一始点最短経路問題(SSSP)を解くアルゴリズム。到達するまでのコストが小さい方からコストを伝搬させていく。

Pythonでは標準の heapq モジュールの heappush と heappop を使えば実現できる。

queue モジュールに PriorityQueue が存在するが heapq モジュールを使う方が高速。

計算量

\(O((|E| + |V|) \log |V|)\)

実装

# V: 頂点数
# g[v] = {(w, cost)}:
#     頂点vから遷移可能な頂点(w)とそのコスト(cost)
# r: 始点の頂点
 
from heapq import heappush, heappop
INF = 10**10
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))

Verified

  • AOJ: "GRL_1_A: Shortest Path - Single Source Shortest Path": source (Python2, 1.98sec)

  • AOJ: "ALDS1_12_C: Graph II - Single Source Shortest Path II": source (Python3, 0.45sec)

queue.PriorityQueue を用いた実装

  • AOJ: "ALDS1_12_C: Graph II - Single Source Shortest Path II": source (Python3, 0.55sec)

戻る