ダイクストラ法とは？仕組み・コード・計算量をわかりやすく解説

ダイクストラ法が解く問題

幅優先探索は辺の数が最小の経路を見つけますが、道路、ネットワークの回線、航空便には、それぞれ異なる距離、コスト、遅延があります。ダイクストラ法は、こうした重み付きグラフでの単一始点最短経路問題を解きます。開始ノードを与えると、他のすべてのノードへの最小の合計コストと、それを実現する経路が求まります。

エッガー・ダイクストラ（Edsger W. Dijkstra）は、1959年に論文 "A note on two problems in connexion with graphs" でこのアルゴリズムを発表しました。

考え方を言葉で説明すると

1. 開始ノードの距離を 0、ほかのすべてのノードの距離を無限大にします。
2. 未確定のノードのうち距離が最小のものを選びます。そのノードの距離はここで確定します。
3. 重み w の各出辺 u → v を緩和します。dist[u] + w < dist[v] なら dist[v] = dist[u] + w に更新し、v の親として u を記録します。
4. 到達可能なすべてのノードが確定するまで、手順2と3を繰り返します。

なぜ最小の距離は確定してよいのでしょうか。そのノードに至るほかの経路は、距離がすでに同じかそれ以上のノードを経由しなければならず、重みが非負なら残りの辺は費用を増やすだけだからです。

具体例で一歩ずつ確認

辺 A→B（4）、A→C（1）、C→B（2）、B→D（1）、C→D（5）、D→E（3）を持つ有向グラフです。A から始めます。

B は、直接の辺でまず距離 4 になり、その後 C 経由で 3 に改善されます。E への最短経路は A → C → B → D → E で、合計コストは 1 + 2 + 1 + 3 = 7 です。

heapqを使ったPythonでの実装

Pythonの heapq モジュールは二分最小ヒープを提供します。「キーの減少」操作の代わりに、距離が改善されるたびに新しい (distance, node) のペアをプッシュし、古くなったペアは取り出したときに読み飛ばします。これを遅延削除（lazy deletion）と呼びます。

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

特定の目的地までの経路を得るには、親へのリンクを開始ノードまでたどります。

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

1つの目的地までの距離だけが必要なら、その目的地がヒープから取り出された時点で探索を打ち切れます。その時点で距離は確定しているからです。

時間計算量と空間計算量

空間計算量は、グラフ、距離と親の対応表、ヒープを合わせて O(V + E) です。

バリエーションとよくある間違い

• if d > dist[u]: continue のチェックを忘れても誤りにはなりませんが、古い要素まで処理してしまい、大幅に遅くなることがあります。
• (distance, node) ではなくノードだけをプッシュすると、ヒープの順序が意味をなさなくなります。
• ノードが比較できないオブジェクトの場合、距離が同じだと heapq がノード同士を比較して TypeError を起こします。一意のカウンタを使って (distance, counter, node) をプッシュしてください。
• A*探索は、優先度にヒューリスティックを加えたダイクストラ法です。残りの距離のよい推定値があれば、探索するノード数を減らせます。
• 双方向ダイクストラ法は、開始ノードとゴールの両方から探索を行い、2つの探索が出会ったところで終了します。

使う場面と実世界での用途

• ルーティング：OSPFやIS-ISなどのリンクステート型ルーティングプロトコルは、ダイクストラ法に基づく最短経路優先（SPF）計算を行います。
• 地図とナビゲーション：実運用のシステムでは、ダイクストラ型の探索に前処理を組み合わせています。
• コーディング面接の問題：ネットワーク遅延時間、最安の航空券（経由回数の制限付き）、グリッドでの最小労力の経路、グラフ上の「合計コスト最小」を求めるあらゆる問題。