ダイクストラアルゴリズム徹底解説：非負グラフの最短経路を効率的に求める基本手法と実装ガイド

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

概要 — ダイクストラアルゴリズムとは

ダイクストラアルゴリズム（Dijkstra's algorithm）は、グラフ上の「単一始点最短経路問題（single-source shortest paths）」を解く古典的なアルゴリズムです。エッジに非負の重みがある有向・無向グラフに対して、指定した始点から他の全頂点への最短距離を効率的に求めます。1959年にエドガー・ダイクストラによって発表され、現在もネットワーク解析、ルーティング、地図経路探索、最適化問題の基礎として広く使われています。

アルゴリズムの仕組み（直感と手順）

アルゴリズムの本質は「贅沢ではない局所的な選択（greedy choice）」にあります。始点からの現在の推定最短距離（距離ラベル）を保持し、まだ確定していない頂点の中から最小の距離ラベルを持つ頂点を順に確定していきます。確定した頂点から伸びる辺を使って隣接頂点の距離ラベルを更新（緩和：relaxation）することを繰り返します。

  • 初期化：始点の距離を0、その他を∞に設定。
  • 未確定頂点のうち距離が最小の頂点uを選び「確定」する。
  • uからの各辺(u, v)について、dist[v] > dist[u] + w(u,v)なら更新する（緩和）。
  • 全頂点が確定するまで2〜3を繰り返す。

擬似コード

function Dijkstra(Graph, source):
    for each vertex v in Graph:
        dist[v] := +∞
        prev[v] := undefined
    dist[source] := 0
    Q := all vertices in Graph  // 優先度付きキューで扱う

    while Q is not empty:
        u := vertex in Q with smallest dist[u]
        remove u from Q
        for each neighbor v of u:
            alt := dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] := alt
                prev[v] := u
                // 優先度付きキューでは decrease-key を行う
    return dist, prev

正当性（なぜ正しいのか）

正当性の直感は次のとおりです。未確定頂点の中で距離が最小の頂点uを取り出したとき、どの未確定頂点を経由しても始点からuへのより短い経路はあり得ません。もし仮にそのような経路が存在するとすると、その経路に現れる最初の未確定頂点xを考えると、xへの距離はuより小さいはずであり矛盾します。形式的には帰納法で証明できます。重要なのはエッジ重みが非負である点で、負の重みがあるとこの議論は破綻します。

計算量とデータ構造

主な計算コストは「未確定頂点から最小distを持つ頂点を取り出す操作」と「辺の緩和（特に decrease-key）」です。使うデータ構造により以下のようになります：

  • 単純な配列（または接続行列＋線形探索）：O(V^2)。頂点数Vが小さい、または密なグラフに向く。
  • 二分ヒープ（binary heap）や優先度付きキュー＋隣接リスト：O((V + E) log V)。一般的な稀なグラフ（E ≪ V^2）で実用的。
  • フィボナッチヒープを使うと：O(V log V + E)。理論的に最良だが実装が複雑で定数因子も大きい。

実装上、C++のpriority_queueなどで decrease-key を直接サポートしない場合は、新しい候補(dist, vertex)を追加して古いエントリは無視する方法がよく使われます。これでも総計算量は O(E log V) になることが多いです。

制約と注意点

  • 負の重みを含むグラフには使えない。負の重みがある場合は Bellman–Ford アルゴリズムを使って単一始点最短経路や負のサイクル検出を行う。
  • 浮動小数点重みでは丸め誤差に注意。比較によって不安定さが出ることがある。
  • 大規模グラフ（特に経路クエリが頻繁な場面）では、Dijkstra単独では遅い。A*（ヒューリスティック）、双方向探索、コントラクションハイアラーキ（Contraction Hierarchies）などの高速化手法が必要。
  • グラフが非常に密（E ≈ V^2）なら隣接行列＋O(V^2)実装の方が効率的な場合がある。

派生・最適化技術

応用や性能改善のために以下のような手法がよく用いられます：

  • 双方向ダイクストラ：始点と終点の両方から同時に探索して中央で衝突させることで探索空間を削減。
  • A*探索：終点までの推定コスト（ヒューリスティック）を活用して探索を誘導する。ヒューリスティックが一貫性（consistency）を満たせば最短経路が得られる。
  • コントラクションハイアラーキ（CH）：事前処理でグラフを簡略化し、クエリを極めて高速化する手法。道路ネットワークなどに有効。
  • マルチソース／多始点：複数始点からの最短距離を効率的に計算する技術（例えば仮想スーパーソースを使うなど）。

実用例（用途）

  • 地図ナビゲーション（最短経路・所要時間の計算、公共交通のスケジューリング）
  • ネットワークルーティング（OSPFなどの経路選択プロトコル）
  • ロボットの経路計画（A*との組合せが多い）
  • ゲームAI（移動経路の探索）
  • 電力網や物流ネットワークの最適化

簡単な手計算例

例：頂点 {A,B,C,D}、始点A。辺重み：A→B=1、A→C=4、B→C=2、B→D=5、C→D=1。

初期：dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞
1) Aを確定（dist=0）→ B: dist[B]=1, C: dist[C]=4
2) 未確定最小はB(dist=1)を確定 → Cを緩和: dist[C]=min(4,1+2)=3、D: dist[D]=1+5=6
3) 未確定最小はC(dist=3)を確定 → Dを緩和: dist[D]=min(6,3+1)=4
4) D(dist=4)を確定 → 完了
結果：dist[A]=0, B=1, C=3, D=4

まとめ

ダイクストラアルゴリズムは、非負重みグラフにおける単一始点最短経路を効率的に求める基本アルゴリズムです。データ構造の選び方によって計算量や実装の複雑さが変わり、用途やグラフの性質に応じて最適化（双方向探索、A*、事前処理など）を組み合わせるのが一般的です。負の重みがある場合は別のアルゴリズムが必要であること、実装では decrease-key の扱いや数値精度に注意することが重要です。

参考文献

カテゴリー
IT
前の記事
バックトラッキング完全解説：基本概念・実装・最適化・CSPと実用応用New!!
2025年11月20日
次の記事
最短経路アルゴリズムの完全解説：基礎から実務応用まで—Dijkstra・Bellman–Ford・A*・Floyd–Warshall・Johnsonほか主要手法と計算量の比較New!!
2025年11月20日