ダイクストラ法入門：仕組み・擬似コード・計算量と実装最適化ガイド

2025年11月18日 最終更新日時 : 2025年11月18日 エバープレイ編集部

概要 — ダイクストラ法とは何か

ダイクストラ法（Dijkstra法）は、重み付きグラフにおいて単一始点から各頂点への最短経路（最短距離）を効率的に求めるアルゴリズムです。エドガー・W・ダイクストラ（Edsger W. Dijkstra）が1959年に提案したもので、非負重みの辺を持つ有向または無向グラフに適用できます。ネットワークルーティングや地図の経路探索、最適化問題の基礎として広く使われています。

歴史と発明者

ダイクストラ法は1959年にダイクストラによって発表されました。彼の論文では、グラフ上の最短経路問題に対するシンプルで明快なアルゴリズムが提示されており、これが現在広く知られるダイクストラ法の原型です。以後、データ構造（ヒープ）の発展や計算理論の進展により、実装性能や理論的複雑度の改良が進められてきました。

アルゴリズムの直観と原理

ダイクストラ法の基本的なアイディアは、始点から到達可能な頂点のうち「現在確定している最短距離が最小」の頂点を順次確定（取り出す）していき、その頂点を起点に隣接辺を緩和（relaxation）することにより、全頂点の最短距離を決定するというものです。

  • 各頂点に「現在の暫定最短距離」を持たせ、始点は0、その他は無限大（未到達）で初期化する。
  • まだ確定していない頂点の中から最小の暫定距離を持つ頂点 u を取り出し、その距離を確定させる。
  • 頂点 u の全ての隣接頂点 v に対して、u を経由することで到達距離が改善されるか（dist[u] + w(u,v) < dist[v]）をチェックし、改善されれば dist[v] を更新して predecessor を記録する（緩和）。
  • これを全頂点が確定するまで繰り返す。

この手続きは、全ての辺の重みが非負であることを前提に正しく動作します（負の辺があると確定処理の順序が崩れ、誤った距離が確定されることがある）。

擬似コード（典型的な実装）

initialize single source(G, s):
  for each vertex v in G:
    dist[v] = +∞
    prev[v] = NIL
  dist[s] = 0

Dijkstra(G, s):
  Q = 全頂点を格納する優先度付きキュー（キーは dist）
  initialize single source(G, s)
  while Q is not empty:
    u = extract-min(Q)         // 最小の dist を持つ頂点を取り出す
    for each neighbor v of u:
      if dist[u] + w(u, v) < dist[v]:
        dist[v] = dist[u] + w(u, v)
        prev[v] = u
        decrease-key(Q, v, dist[v])

ここで prev 配列を使えば各頂点への最短経路（経路復元）を構築できます。

正当性のスケッチ（なぜ正しいか）

正当性は主に「貪欲選択」と「緩和操作」による不変式（invariant）を使って示されます。キーとなる観察は次の通りです。

  • ある時点で取り出された頂点 u の dist[u] は、始点から u への最短距離に等しい（これを証明するために帰納法を使う）。
  • もし dist[u] が最短距離より大きければ、始点から u へ到るある最短経路上にまだキューに残っている頂点が存在し、それを先に取り出すべきであるが、u が最小の暫定値として選ばれたことに矛盾する。

このため、取り出された頂点の距離は確定しており、隣接辺の緩和によって他の頂点の暫定距離が更新され、最終的に全頂点の最短距離が確定します。重要な前提は「辺の重みが非負」であることです。

計算量と実装の選択

ダイクストラ法の計算量は用いるデータ構造によって変わります。グラフは頂点数を V、辺数を E とします。

  • 単純配列（または線形検索で最小distを選ぶ）で実装する場合：O(V^2)。これは頂点数が少ない密グラフ（E が V^2 に近い）に向いています。
  • 二分ヒープ（binary heap）を使う場合：extract-min が O(log V)、decrease-key が O(log V) で、全体で O((V + E) log V)。一般的にスパースグラフ（E は O(V)〜O(V log V) 程度）で有効です。実際には O(E log V) と表現されることが多いです。
  • フィボナッチヒープ（Fibonacci heap）を使う場合：decrease-key が O(1)（償却）、extract-min が O(log V) で、全体は O(V log V + E)。理論的には最良ですが、実装が複雑で定数因子が大きいため実用では二分ヒープの方が高速な場合も多いです。
  • 特定条件下のアルゴリズム：辺の重みが非負の整数かつ最大重みが小さい場合、Dialのバケット法などを使って O(E + W V)（または O(E + max_weight) に近い）にできることがあります。Thorupのアルゴリズムは整数重みの無向グラフで線形時間を達成しますが実装は高度です。

拡張・派生アルゴリズムと実用的最適化

  • 双方向ダイクストラ（Bidirectional Dijkstra）: 始点側と終点側の両方から同時に探索を進めて早期に停止することで平均的に高速化できます（単一終点問題の場合）。
  • A*（A-star）: ヒューリスティック関数を導入することで目標指向の探索を行い、ダイクストラを一般化したもの。保証付きの最短経路を得るには「過小評価（admissible）」なヒューリスティックが必要です。
  • ジョンソン法（Johnson's algorithm）: グラフに負の重みが含まれるが負サイクルがない場合、Bellman–Fordで再重み付けを行い各頂点を始点にしてダイクストラを複数回実行することで全点対最短経路を効率よく求められます。
  • 並列化・外部メモリ: 大規模グラフ（道路ネットワーク等）では、マルチスレッド化や外部メモリ用アルゴリズム、また階層化・事前処理（コンパクト化経路検索、Contraction Hierarchies など）によって応答性を向上させます。

制約・注意点

  • 辺の重みは非負であることが必須（負の辺がある場合、Bellman–FordやJohnsonの再重み付けを検討する）。
  • 数値精度: 浮動小数点を重みに使う場合、比較・加算で丸め誤差が入り得る。等価判定や閾値には注意が必要です。
  • 大規模データ: メモリ使用量（dist, prev, 隣接リスト、キュー）は無視できないため、実装ではメモリ効率やデータ局所性を考慮する必要があります。
  • 最短経路の一意性: 同じ最短距離を持つ複数経路がある場合、prev 配列の取り扱いで返される経路は一つに固定される。全ての最短経路を列挙するには別途アルゴリズムが必要です。

具体例（短い説明）

始点 A から B, C, D へ向かう小さなグラフを考えると、初期状態では dist[A]=0, 他は ∞。A を取り出して隣接頂点の距離を更新し、次に最小の暫定distを持つ頂点を取り出して…という手順を経て、最終的に各頂点の dist が確定します。経路は prev をたどれば復元できます。

実世界での利用例

  • ルーティングプロトコル: OSPF（Open Shortest Path First）はリンクステート型で各ルータがダイクストラ法を使って最短経路を計算します（RFCに規定）。
  • 地図・ナビゲーション: 道路ネットワーク上で最短時間や最短距離を求める基礎アルゴリズムとして使用され、A* や事前処理を組み合わせることが多いです。
  • 輸送・物流、ネットワーク設計、ゲームAI など多数の分野で用いられます。

まとめ

ダイクストラ法は、非負重みグラフ上の単一始点最短経路問題を解くための古典的かつ実用的なアルゴリズムです。単純で理解しやすく、多くの応用で第一選択となります。実装ではデータ構造（ヒープの種類）、グラフのサイズや密度、重みの性質に応じて最適化や別手法（A*、双方向探索、Johnson法など）を検討することが重要です。

参考文献

カテゴリー
IT
前の記事
João Donato（ジョアン・ドナート）入門：ボサ・ノヴァ巨匠の代表曲・名盤と聴きどころNew!!
2025年11月18日
次の記事
ナラ・レオン入門：ボサノヴァのミューズからMPBへ—代表曲・名盤と聴きどころガイドNew!!
2025年11月18日