ダイクストラ法

ダイクストラ法#

ダイクストラ法（Dijkstra’s algorithm） は、グラフ上の単一始点最短経路問題を解くアルゴリズムである。 1956年にエドガー・ダイクストラが考案した。

概要#

重み付き有向グラフ（または無向グラフ）において、始点から各頂点への最短距離を求める。 辺の重みが非負であることが前提条件となる。

アルゴリズムの手順#

始点の距離を \(0\)、他のすべての頂点の距離を \(\infty\) に初期化する
未確定の頂点の中から距離が最小の頂点 \(v\) を選ぶ
\(v\) の各隣接頂点 \(u\) に対して、\(v\) を経由したときの距離が現在の距離より小さければ更新する（緩和操作）
\(v\) を確定済みにする
未確定の頂点がなくなるまで 2〜4 を繰り返す

https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif — Fig. 2 ダイクストラ法の動作イメージ（Wikipedia より）#

計算量#

実装方法	時間計算量	空間計算量
隣接行列 + 線形探索	\(O(V^2)\)	\(O(V^2)\)
隣接リスト + 二分ヒープ	\(O((V + E) \log V)\)	\(O(V + E)\)
隣接リスト + フィボナッチヒープ	\(O(E + V \log V)\)	\(O(V + E)\)

\(V\)：頂点数、\(E\)：辺数

密なグラフ（\(E \approx V^2\)）では隣接行列 + 線形探索が有利
疎なグラフでは優先度付きキュー（ヒープ）を使った実装が効率的
実用上は 隣接リスト + 二分ヒープ が最もよく使われる

実装例#

import heapq
from collections import defaultdict

def dijkstra(graph: dict, start: int) -> dict:
    """
    Parameters
    ----------
    graph : dict
        隣接リスト。graph[u] = [(v, weight), ...] の形式
    start : int
        始点の頂点番号

    Returns
    -------
    dict
        各頂点への最短距離。到達不能な頂点は float('inf')
    """
    dist = defaultdict(lambda: float("inf"))
    dist[start] = 0
    heap = [(0, start)]  # (distance, vertex)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # すでにより短い距離で確定済み
        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dict(dist)


# --- 使用例 ---
#
#     1
#   /   \
#  0  2  3
#   \   /
#    2
#
graph = defaultdict(list)
edges = [(0, 1, 1), (0, 2, 4), (1, 2, 2), (1, 3, 5), (2, 3, 1)]
for u, v, w in edges:
    graph[u].append((v, w))
    graph[v].append((u, w))  # 無向グラフ

dist = dijkstra(graph, start=0)
print("始点 0 からの最短距離:")
for v in sorted(dist):
    print(f"  頂点 {v}: {dist[v]}")

始点 0 からの最短距離:
  頂点 0: 0
  頂点 1: 1
  頂点 2: 3
  頂点 3: 4

経路復元#

最短経路そのものを復元したい場合は、各頂点の直前の頂点（predecessor）を記録しておく。

def dijkstra_with_path(graph: dict, start: int) -> tuple[dict, dict]:
    dist = defaultdict(lambda: float("inf"))
    prev = {}
    dist[start] = 0
    heap = [(0, start)]

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

    return dict(dist), prev


def reconstruct_path(prev: dict, start: int, goal: int) -> list[int]:
    path = []
    v = goal
    while v != start:
        if v not in prev:
            return []  # 到達不能
        path.append(v)
        v = prev[v]
    path.append(start)
    return path[::-1]


dist, prev = dijkstra_with_path(graph, start=0)
path = reconstruct_path(prev, start=0, goal=3)
print(f"0 → 3 の最短経路: {' → '.join(map(str, path))}, 距離: {dist[3]}")

0 → 3 の最短経路: 0 → 1 → 2 → 3, 距離: 4

応用例#

1. カーナビ・地図サービス#

道路ネットワークを重み付きグラフとして表現し、出発地から目的地への最短（最速）経路を計算する。 Google Maps や OSRM などで類似のアルゴリズムが使われている。

2. ネットワークルーティング（OSPF）#

インターネットのリンク状態型ルーティングプロトコル OSPF（Open Shortest Path First）はダイクストラ法を用いてルーティングテーブルを構築する。

3. ゲームの経路探索#

ゲームのマップを格子グラフとして扱い、キャラクターの移動経路を求める。実際にはヒューリスティックを加えた A* アルゴリズム がよく使われる（ダイクストラ法は A* のヒューリスティックを 0 にした特殊ケース）。

4. 通信ネットワークの遅延最小化#

通信パスの遅延（重み）を最小化する経路選択。

5. 金融・サプライチェーン最適化#

コスト・リスクを辺の重みとして最小コスト経路を求める。

注意点・制限#

負の辺の重みには対応しない。負の重みがある場合は Bellman–Ford 法を使う。
負の閉路がある場合は動作しない（最短経路が存在しないため）。
全頂点間の最短経路を求める場合は Floyd–Warshall 法（\(O(V^3)\)）や、すべての始点からダイクストラを実行する方法（\(O(VE \log V)\)）を使う。