ダイクストラ法

ダイクストラ法とは

ダイクストラ法（Dijkstra's algorithm）は、グラフ理論における重要なアルゴリズムの一つで、特に単一始点最短経路問題を解くために用いられます。このアルゴリズムは、グラフ内の特定の始点から他のすべての頂点への最短経路を効率的に見つけ出すことができます。

ダイクストラ法の概要

1959年にエドガー・ダイクストラによって考案されたこのアルゴリズムは、その応用範囲の広さから、現在でも多くの分野で利用されています。例えば、インターネットのルーティングプロトコルであるOSPFや、カーナビゲーションシステムの経路探索、鉄道の経路案内システムなど、私たちの日常生活に密接に関わる技術にも活用されています。

ダイクストラ法は、グラフの辺に非負の重みが付与されている場合に最適に機能します。これは、現実世界の多くのシナリオ、例えば道路の長さやネットワークの遅延時間などが非負の値で表現されることに対応しています。

他のアルゴリズムとの比較

ダイクストラ法は非常に有用なアルゴリズムですが、状況によっては他のアルゴリズムがより適している場合があります。

Aアルゴリズム:* 最短経路の推定値を事前に知っている場合は、ダイクストラ法の改良版であるAアルゴリズムを使用することで、より効率的に最短経路を求めることが可能です。
幅優先[[探索]]: 辺の重みがすべて同じである場合、幅優先[[探索]]の方がより高速に最短経路を計算できます。
Thorupのアルゴリズム: 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能ですが、実用性はあまり高くありません。
ベルマン-フォード法: 辺の重みに負数が含まれる場合は、ベルマン-フォード法を使用する必要があります。ダイクストラ法は負の重みを持つ辺には対応できません。

ダイクストラ法の擬似コード

ダイクストラ法の基本的な擬似コードは以下の通りです。


// 初期化
各頂点 v ∈ V に対して、
d(v) ← (v = s ならば 0、それ以外は ∞)
prev(v) ← 「無し」
Q に V の頂点を全て追加

// 本計算
while (Q が空ではない)
u ← Q から d(u) が最小である頂点を取り出す
for each (u からの辺がある各頂点 v ∈ V)
alt ← d(u) + length(u, v)
if (d(v) > alt)
d(v) ← alt
prev(v) ← u


ここで、

`Q` は頂点の集合を表します。
`u` と `v` はグラフの頂点を表します。
`G = (V, E)` はグラフ、`s` は始点を表します。
`length(u, v)` は頂点 `u` から `v` への辺の長さを表します。
`d(v)` は始点 `s` から頂点 `v` への最短経路の長さを表します。
`prev(v)` は最短経路をたどる際の頂点 `v` の直前の頂点を表します。

優先度付きキューの利用

ダイクストラ法の効率を向上させるために、優先度付きキューを使用することが一般的です。優先度付きキューは、`d(u)` の値に基づいて頂点を管理し、最小の `d(u)` を持つ頂点を効率的に取り出すことを可能にします。優先度付きキューを使用する場合、擬似コードは以下のように更新されます。


// 初期化
for (v ← V)
d(v) ← (v = s ならば 0、それ以外は ∞)
prev(v) ← 「無し」
Q(v) ← d(v)

// 本計算
while (Q が空集合ではない)
u ← Q から d(u) が最小である頂点 u を取り出す
for each (u からの辺がある各 v ∈ V)
alt ← d(u) + length(u, v)
if (d(v) > alt)
d(v) ← alt
prev(v) ← u
Q(v) ← alt

計算量

ダイクストラ法の計算量は、使用するデータ構造に大きく依存します。以下に一般的な計算量を示します。

オリジナル: O(V²)
優先度付きキュー（二分ヒープ）: O((E + V) log V)
優先度付きキュー（フィボナッチヒープ）: O(E + V log V)

ここで、Vは頂点の数、Eは辺の数を表します。優先度付きキューを使用することで、特に大規模なグラフにおいて計算時間を大幅に短縮することができます。

アルゴリズムの詳細な解説

概念的な説明

ダイクストラ法を理解するために、グラフを物理的なモデルで考えてみましょう。各頂点をビー玉、辺を紐で表現したグラフを想像します。スタート地点のビー玉を持ち上げると、グラフは重力に従って落下しますが、スタート地点に近いビー玉から順番に止まっていきます。ゴール地点のビー玉が止まった時、それはスタート地点から紐で一直線に結ばれており、これが最短経路になります。

ダイクストラ法は、この物理的な現象をコンピュータ上でシミュレーションしています。

アルゴリズムのステップ

1. 初期化:
すべての頂点に対して、スタート地点からの距離を無限大に設定します。
スタート地点自身の距離は0に設定します。
各頂点の「直前の頂点」を「無し」に設定します。
すべての頂点を未訪問の頂点の集合`Q`に追加します。
2. ループ:
`Q`が空になるまで、以下のステップを繰り返します。
`Q`から、スタート地点からの距離が最小である頂点`u`を取り出します。
`u`に隣接するすべての頂点`v`に対して、次の操作を行います。
スタート地点から`u`を経由して`v`に到達する場合の距離`alt`を計算します (`alt = d(u) + length(u, v)`)。
もし、`alt`が現在`v`に設定されている距離よりも小さければ、`v`の距離を`alt`で更新し、`v`の「直前の頂点」を`u`に更新します。
3. 結果:
すべての頂点への最短経路とその距離が計算されます。

データの管理

ダイクストラ法では、以下のデータを管理します。

訪問済み頂点集合`H`: 落下が停止した頂点の集合
未訪問頂点集合`A`: `H`に隣接する頂点の集合
各頂点`v`への最短距離 `d(v)`: スタート地点から`v`への最短距離。
各頂点`v`の直前の頂点 `w_v`: 最短経路における`v`の直前の頂点。

アルゴリズムの更新

次に落下が停止する頂点`u`を`A`の中から選択します。この時、`d(u)`が最小となる頂点を選びます。
`u`を`H`に追加し、`A`から削除します。`u`に隣接する未訪問の頂点を`A`に追加します。
`u`に隣接するすべての頂点`v`に対し、`d(v)`の値を更新します。もし、`d(v) > d(u) + length(u, v)`であれば、`d(v)`を`d(u) + length(u, v)`で更新し、`w_v`を`u`に更新します。

まとめ

ダイクストラ法は、グラフ理論における基本的なアルゴリズムの一つであり、その効率性と実用性から、多くの分野で広く利用されています。このアルゴリズムを理解することで、様々な問題解決に役立つでしょう。

参考資料

Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269 ～ 271.
コルテ, B.、フィーゲン, J.『組合せ最適化 : 理論とアルゴリズム』（第2版）シュプリンガー・ジャパン、2009年、184–185頁。ISBN 978-4431100218。

関連項目

最良優先探索
Aアルゴリズム
均一コスト探索
最短経路問題
動的計画法
ベルマン-フォード法

もう一度検索