ダイクストラ法 - データサイエンス関連+αのメモ

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

概要¶

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

アルゴリズムの手順¶

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

計算量¶

実装方法	時間計算量	空間計算量
隣接行列 + 線形探索	$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)$ ）を使う。