ダイクストラ法 (Dijkstra’s Algorithm)

概要

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

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

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
dist = [INF]*V
que = [(0,r)]
dist[r] = 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)

Radix Heapによるダイクストラ法

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

参考ページ