Dijkstra アルゴリズムとは？ 最短経路を見つける仕組みを理解しよう

By /

Dijkstraアルゴリズムとは？ 最短経路を見つける仕組みを理解しよう

1. はじめに：最短経路問題の世界へようこそ

私たちの日常生活は、常に「最適な道筋」を探す旅のようなものです。目的地までの最短時間で移動する方法、インターネットでデータが最も早く届く経路、物流ネットワークでコストを最小限に抑える配送ルートなど、様々な場面で「最短経路」を求める必要に迫られます。このような問題は、コンピュータサイエンスの世界では「最短経路問題」として知られており、グラフ理論における最も基本的な問題の一つです。

グラフとは、点（頂点、ノード）と、その点を結ぶ線（辺、エッジ）から構成される数学的な構造です。地図上の都市を頂点、都市間の道路を辺と見なし、道路の長さや移動時間を辺の「重み」とすれば、現実世界のナビゲーション問題はグラフ上の最短経路問題として表現できます。通信ネットワークにおけるコンピュータやルーターを頂点、通信回線を辺とし、その帯域幅や遅延を重みとすれば、データルーティングの問題も同様にグラフ問題となります。

この最短経路問題を解くための、最も有名で広く使われているアルゴリズムの一つが、エドガー・ダイクストラによって1956年に考案された「Dijkstraアルゴリズム」です。Dijkstraアルゴリズムは、「単一始点最短経路問題」を解くためのアルゴリズムとして知られています。これは、「ある一つの特定の始点から、グラフ内の他のすべての頂点への最短経路とその距離を求める」という問題です。

このアルゴリズムは非常に直感的でありながら、多くの実用的な問題に応用できる強力なツールです。本記事では、Dijkstraアルゴリズムがどのように機能し、なぜ正しく最短経路を見つけられるのか、その仕組みを詳細かつ分かりやすく解説していきます。約5000語にわたる解説を通じて、アルゴリズムの核心を理解し、その応用可能性を感じ取っていただければ幸いです。

2. Dijkstraアルゴリズムの直感的な考え方

Dijkstraアルゴリズムの基本的な考え方は非常にシンプルです。「始点から近い頂点から順に、最短距離を確定していく」という貪欲なアプローチに基づいています。

想像してみてください。あなたは迷路の入り口（始点）に立っています。出口（他の頂点）へ向かう最短経路を見つけたいのですが、迷路全体の地図は持っていません。手元にあるのは、現在地から直接行ける場所（隣接する頂点）までの距離の情報だけです。

あなたはまず、現在地（始点）から直接行ける場所の中で、一番近い場所に行きます。そこに着いたら、そこからさらに直接行ける場所への距離を調べます。このとき、以前調べた場所への新しい経路が見つかるかもしれません。もし新しい経路の方が、以前記録した距離よりも近ければ、その場所への「暫定的な最短距離」を更新します。

このプロセスを繰り返します。つまり、「現在までに発見された、まだ確定していない頂点までの距離」の中で、最も短い距離を持つ頂点を選びます。そして、その頂点に移動し、そこから行ける場所までの距離を調べ、必要であれば暫定距離を更新するのです。一度「最も短い暫定距離を持つ」として選ばれた頂点への距離は、それ以上短くなることはありません。なぜなら、もしそれより短い経路が存在するなら、その経路の最後の頂点（まだ確定していない頂点）が、選ばれた頂点よりも短い暫定距離を持っているはずだからです。これは、Dijkstraアルゴリズムが「負の重み」を持つ辺が存在しないグラフでのみ正しく機能することを示唆しています。負の重みがあると、すでに確定した頂点への距離が、後から見つかる負の重みを含む経路によってさらに短くなる可能性があるからです。

Dijkstraアルゴリズムは、このように「未訪問」の頂点の中から、現在見つかっている「暫定的な最短距離」が最小である頂点を一つ選び出し、その頂点を「訪問済み（最短距離が確定）」として扱います。そして、その確定した頂点に隣接する未訪問の頂点に対して、始点からの距離を再計算（緩和）し、暫定距離を更新していきます。これを、すべての頂点が訪問済みとなるか、到達不能な頂点以外の暫定距離が無限大のまま残るまで繰り返します。

このアプローチが「貪欲法」と呼ばれるのは、各ステップでその時点での最善の選択（最も暫定距離が短い頂点の選択）を行い、それが最終的な最適解（最短経路）につながると信じて進むからです。負の重みがなければ、この貪欲な選択が全体の最適解を導くことが保証されます。

3. アルゴリズムの詳細なステップバイステップ解説

Dijkstraアルゴリズムを実装し、その動作を正確に理解するためには、いくつかのデータ構造と明確な手順が必要です。対象とするグラフは、頂点の集合Vと辺の集合Eからなり、各辺(u, v)には非負の重みw(u, v)が与えられているとします。

3.1. 必要なデータ構造

アルゴリズムの実行中に、以下の情報を管理する必要があります。

  1. dist[v]: 始点から各頂点vまでの、現在見つかっている最短距離（暫定距離）。最初は始点以外のすべての頂点について無限大(∞)に初期化されます。始点自身の距離は0です。
  2. prev[v]: 始点から頂点vへの最短経路において、vの直前に位置する頂点（先行頂点）。この情報を使って、アルゴリズム終了後に最短経路を逆順にたどって再構築できます。最初はすべての頂点について未定義としておきます。
  3. Q: まだ最短距離が確定していない頂点の集合。通常は「優先度キュー (Priority Queue)」として実装されます。優先度キューは、要素（ここでは頂点）とその優先度（ここでは頂点までの現在の暫定距離）を保持し、優先度が最も高い要素（ここでは暫定距離が最小の頂点）を効率的に取り出すことができるデータ構造です。

3.2. アルゴリズムの手順

Dijkstraアルゴリズムのステップは以下のようになります。

ステップ1: 初期化 (Initialization)

  • グラフGの各頂点vに対して、以下の値を設定します。
    • dist[v] = ∞ (無限大): 始点以外のすべての頂点への距離を無限大に設定します。これは、まだどの経路も見つかっていないことを意味します。
    • prev[v] = undefined: すべての頂点の先行頂点を未定義とします。
  • 始点sに対して、以下の値を設定します。
    • dist[s] = 0: 始点自身への距離は0です。
  • 未訪問の頂点の集合Qに、グラフのすべての頂点を追加します。
  • 優先度キューを使用する場合、最初は始点sを距離0として追加し、他の頂点は距離∞として追加します（または、始点のみを追加し、他の頂点は必要に応じて後で追加・更新します。実装によって異なりますが、一般的にはすべての頂点を最初は無限大の距離で追加しておくと便利です）。

ステップ2: メインループ (Main Loop)

Qが空になるまで、以下の処理を繰り返します。

  • (a) 最小距離の頂点を取り出し (Extract-Min): Qの中から、dist値が最小である頂点uを取り出します。これは、優先度キューの機能を使って効率的に行います。取り出された頂点uは、これ以降「最短距離が確定した頂点」として扱われます。Qからの取り出しは、その頂点を未訪問集合から既訪問集合へ移すことを意味します。
  • 注意: もしdist[u]が無限大であれば、これは始点から頂点uには到達不可能であることを意味します。この場合、これ以上処理を続けても、残りの未訪問の頂点への有限の経路は見つかりません。したがって、ここでループを終了することも可能です。
  • (b) 隣接頂点の緩和 (Relaxation): 取り出した頂点uに隣接する各頂点v（つまり、辺(u, v)が存在するすべてのv）について、以下の処理を行います。
    • 新しい経路を通った場合の距離を計算します: alt = dist[u] + w(u, v)
    • もし、計算された新しい距離altが、現在記録されている頂点vまでの距離dist[v]よりも短い場合、距離と先行頂点を更新します。
      • dist[v] = alt
      • prev[v] = u
    • 優先度キューの更新: 優先度キューQ内で頂点vの情報が管理されている場合、vの優先度（dist[v]）が更新されたことをキューに通知します。これにより、キュー内のvの正しい位置が維持されます。もしvがまだキューに明示的に追加されていなかった場合は、新しい距離で追加します。（実装によっては、更新は単に新しい距離で再度追加することで行われ、最小距離のものが最初に取り出されることで古いエントリは無視されます。）

ステップ3: 終了 (Termination)

Qが空になったとき、アルゴリズムは終了します。この時点で、各頂点vに対するdist[v]は、始点sから頂点vへの最短距離を示しています。prev[v]をたどることで、最短経路を再構築できます。

3.3. 擬似コード

上記のステップを擬似コードで表現すると以下のようになります。

“`
Dijkstra(Graph G, Source s):
// ステップ1: 初期化
For each vertex v in G.V:
dist[v] = infinity // 全ての頂点への距離を無限大に初期化
prev[v] = undefined // 全ての頂点の先行頂点を未定義に初期化

dist[s] = 0 // 始点sへの距離は0

Q = new PriorityQueue() // 優先度キューを作成
For each vertex v in G.V:
Q.insert(v, dist[v]) // 各頂点をその距離を優先度としてキューに追加

// ステップ2: メインループ
While Q is not empty:
u = Q.extract_min() // Qから最小距離の頂点uを取り出す

// 到達不可能な頂点はスキップ（オプションだが効率的）
// If dist[u] == infinity:
//   break

// uに隣接する各頂点vに対して緩和処理を行う
For each vertex v adjacent to u:
  // edge weight from u to v is w(u, v)
  alt = dist[u] + w(u, v)
  If alt < dist[v]:
    dist[v] = alt // 距離を更新
    prev[v] = u   // 先行頂点を更新
    Q.decrease_key(v, alt) // Q内でvの優先度を更新 (必要なら)

// ステップ3: 終了
// dist[]配列に始点sからの各頂点への最短距離が格納されている
// prev[]配列を使って最短経路を再構築できる
“`

補足: 優先度キューの実装方法によっては、decrease_key操作が直接提供されない場合があります。その場合、距離が更新された頂点は、新しい距離で再度キューに追加されることがあります。extract_minは常に最小距離の頂点（たとえそれが古いエントリであっても）を取り出しますが、メインループの緩和処理はdist[v]の最新の値を見ているため、古いエントリが取り出されても問題なく動作します。ただし、キューに多くの重複エントリが蓄積される可能性があり、効率に影響を与える可能性があります。標準的なライブラリで提供される優先度キューは、通常decrease_keyに相当する機能（要素の削除と再挿入、または要素の値の更新とヒープ構造の調整）を持っています。

4. 具体例で理解を深める

実際のグラフを使って、Dijkstraアルゴリズムの動作をステップごとに追ってみましょう。以下の有向グラフを考えます。頂点はA, B, C, D, Eの5つ、辺には非負の重みがついています。

A --2--> B --1--> C
| \ | ^
| \ | |
6 3 2 5
| \ | |
v \ v |
D --1--> E --?---/ (辺なし or 非常に大きい重みと考える)

（注：EからCへの辺は、この例では存在しないか、あるいは非常に大きな重みを持つと仮定します。図には点線で5と書いてありますが、これは別の例の名残か、単なる到達不能性を示すものとして、ここでは無視します。）

始点をAとします。

ステップ0: 初期状態

  • dist[A] = 0, prev[A] = undefined
  • dist[B] = ∞, prev[B] = undefined
  • dist[C] = ∞, prev[C] = undefined
  • dist[D] = ∞, prev[D] = undefined
  • dist[E] = ∞, prev[E] = undefined
  • Q = {(A, 0), (B, ∞), (C, ∞), (D, ∞), (E, ∞)} (優先度キュー、タプルは(頂点, 距離)を表す)

ステップ1: 最小距離の頂点を取り出し

  • Qの中で最小距離はAの0です。Aを取り出します。
  • u = A, dist[A]が確定します (0)。
  • Qの状態: {(B, ∞), (C, ∞), (D, ∞), (E, ∞)}

ステップ1: 緩和 (頂点Aから)

  • Aに隣接する頂点はBとDです。

    • 頂点Bに対して:
      • 辺(A, B)の重みは2です。
      • 新しい距離 alt = dist[A] + w(A, B) = 0 + 2 = 2
      • 現在の dist[B] は ∞ です。2 < ∞ なので更新します。
      • dist[B] = 2, prev[B] = A
      • Q内でBの距離を更新: Q = {(B, 2), (C, ∞), (D, ∞), (E, ∞)}
    • 頂点Dに対して:
      • 辺(A, D)の重みは6です。
      • 新しい距離 alt = dist[A] + w(A, D) = 0 + 6 = 6
      • 現在の dist[D] は ∞ です。6 < ∞ なので更新します。
      • dist[D] = 6, prev[D] = A
      • Q内でDの距離を更新: Q = {(B, 2), (C, ∞), (D, 6), (E, ∞)}

  • 現在の状態:

    • dist = {A: 0, B: 2, C: ∞, D: 6, E: ∞}
    • prev = {A: undef, B: A, C: undef, D: A, E: undef}
    • Q = {(B, 2), (D, 6), (C, ∞), (E, ∞)} (優先度順に並べ替えると)

ステップ2: 最小距離の頂点を取り出し

  • Qの中で最小距離はBの2です。Bを取り出します。
  • u = B, dist[B]が確定します (2)。
  • Qの状態: {(D, 6), (C, ∞), (E, ∞)}

ステップ2: 緩和 (頂点Bから)

  • Bに隣接する頂点はCとEです。

    • 頂点Cに対して:
      • 辺(B, C)の重みは1です。
      • 新しい距離 alt = dist[B] + w(B, C) = 2 + 1 = 3
      • 現在の dist[C] は ∞ です。3 < ∞ なので更新します。
      • dist[C] = 3, prev[C] = B
      • Q内でCの距離を更新: Q = {(D, 6), (C, 3), (E, ∞)}
    • 頂点Eに対して:
      • 辺(B, E)の重みは2です。
      • 新しい距離 alt = dist[B] + w(B, E) = 2 + 2 = 4
      • 現在の dist[E] は ∞ です。4 < ∞ なので更新します。
      • dist[E] = 4, prev[E] = B
      • Q内でEの距離を更新: Q = {(D, 6), (C, 3), (E, 4)}

  • 現在の状態:

    • dist = {A: 0, B: 2, C: 3, D: 6, E: 4}
    • prev = {A: undef, B: A, C: B, D: A, E: B}
    • Q = {(C, 3), (E, 4), (D, 6)} (優先度順に並べ替えると)

ステップ3: 最小距離の頂点を取り出し

  • Qの中で最小距離はCの3です。Cを取り出します。
  • u = C, dist[C]が確定します (3)。
  • Qの状態: {(E, 4), (D, 6)}

ステップ3: 緩和 (頂点Cから)

  • Cに隣接する頂点はありません（図によるとEからCへの辺は存在しないか無視するため）。

  • 緩和処理は行われません。

  • 現在の状態:

    • dist = {A: 0, B: 2, C: 3, D: 6, E: 4}
    • prev = {A: undef, B: A, C: B, D: A, E: B}
    • Q = {(E, 4), (D, 6)} (優先度順に並べ替えると)

ステップ4: 最小距離の頂点を取り出し

  • Qの中で最小距離はEの4です。Eを取り出します。
  • u = E, dist[E]が確定します (4)。
  • Qの状態: {(D, 6)}

ステップ4: 緩和 (頂点Eから)

  • Eに隣接する頂点はDです（辺(E, D)の重みは不明ですが、例の図ではDからEへの辺があります。もしEからDへの辺もあるなら緩和を行います。ここでは図に従い辺(E, D)の重みを無限大と仮定するか、あるいは後述のDからの緩和で影響を受けるとして、ここでは緩和対象なしとします。あるいは、辺(E,D)の重みが例えば1だとしましょう）。辺(E, D)の重みを1と仮定します。

    • 頂点Dに対して:
      • 辺(E, D)の重みは1です。
      • 新しい距離 alt = dist[E] + w(E, D) = 4 + 1 = 5
      • 現在の dist[D] は 6 です。5 < 6 なので更新します。
      • dist[D] = 5, prev[D] = E
      • Q内でDの距離を更新: Q = {(D, 5)} (優先度順に並べ替えると)

  • 現在の状態:

    • dist = {A: 0, B: 2, C: 3, D: 5, E: 4}
    • prev = {A: undef, B: A, C: B, D: E, E: B}
    • Q = {(D, 5)}

(元の図の辺(D, E)の重みが1だったので、辺(E, D)の重みも1だと仮定し直しました。もし無向グラフであれば辺(E, D)も重み1になります。有向グラフで辺(E, D)が存在しないなら、この緩和は行われません。ここでは図を元に有向グラフで辺(A,B), (A,D), (B,C), (B,E), (D,E)のみを考えます。辺(D,E)の重みは1です。するとステップ4の緩和対象はEに隣接する辺ですが、Eから出ている辺は図にはありません。したがって、ステップ4の緩和は行われないことになります。上記の例は、図にある辺以外の辺(E,D)を勝手に追加してしまったため、混乱を招いています。元の図の辺だけを考慮し直します。辺は(A,B,2), (A,D,6), (B,C,1), (B,E,2), (D,E,1)です。)

例の再実行 (元の図にある辺のみ使用)

ステップ0: 初期状態 (変更なし)
* dist = {A: 0, B: ∞, C: ∞, D: ∞, E: ∞}
* prev = {A: undef, B: undef, C: undef, D: undef, E: undef}
* Q = {(A, 0), (B, ∞), (C, ∞), (D, ∞), (E, ∞)}

ステップ1: Aを取り出し (dist[A]=0 確定)
* u = A. 隣接: B (重み2), D (重み6)
* B: alt = 0 + 2 = 2. dist[B]=∞ より更新 dist[B]=2, prev[B]=A. Q: update B to (B, 2).
* D: alt = 0 + 6 = 6. dist[D]=∞ より更新 dist[D]=6, prev[D]=A. Q: update D to (D, 6).
* 状態: dist = {A: 0, B: 2, C: ∞, D: 6, E: ∞}, prev = {A: undef, B: A, C: undef, D: A, E: undef}, Q = {(B, 2), (D, 6), (C, ∞), (E, ∞)} -> 優先度順: {(B, 2), (D, 6), (C, ∞), (E, ∞)}

ステップ2: Bを取り出し (dist[B]=2 確定)
* u = B. 隣接: C (重み1), E (重み2)
* C: alt = dist[B] + w(B, C) = 2 + 1 = 3. dist[C]=∞ より更新 dist[C]=3, prev[C]=B. Q: update C to (C, 3).
* E: alt = dist[B] + w(B, E) = 2 + 2 = 4. dist[E]=∞ より更新 dist[E]=4, prev[E]=B. Q: update E to (E, 4).
* 状態: dist = {A: 0, B: 2, C: 3, D: 6, E: 4}, prev = {A: undef, B: A, C: B, D: A, E: B}, Q = {(D, 6), (C, 3), (E, 4)} -> 優先度順: {(C, 3), (E, 4), (D, 6)}

ステップ3: Cを取り出し (dist[C]=3 確定)
* u = C. 隣接: なし
* 状態: dist = {A: 0, B: 2, C: 3, D: 6, E: 4}, prev = {A: undef, B: A, C: B, D: A, E: B}, Q = {(E, 4), (D, 6)}

ステップ4: Eを取り出し (dist[E]=4 確定)
* u = E. 隣接: D (重み1)
* D: alt = dist[E] + w(E, D) = 4 + 1 = 5. 現在の dist[D] は 6 です。5 < 6 なので更新します。
* dist[D] = 5, prev[D] = E
* Q内でDの距離を更新: Q = {(D, 5)}
* 状態: dist = {A: 0, B: 2, C: 3, D: 5, E: 4}, prev = {A: undef, B: A, C: B, D: E, E: B}, Q = {(D, 5)}

ステップ5: Dを取り出し (dist[D]=5 確定)
* u = D. 隣接: E (重み1)
* E: alt = dist[D] + w(D, E) = 5 + 1 = 6. 現在の dist[E] は 4 です。6 は 4 より大きくないので、更新は行いません。
* 状態: dist = {A: 0, B: 2, C: 3, D: 5, E: 4}, prev = {A: undef, B: A, C: B, D: E, E: B}, Q = {}

ステップ6: Qが空になったので終了

最終的な距離と先行頂点:
* dist = {A: 0, B: 2, C: 3, D: 5, E: 4}
* prev = {A: undef, B: A, C: B, D: E, E: B}

最短経路の再構築 (prevを逆にたどる):
* A -> A (距離0)
* B -> A -> B (距離2)
* C -> B -> A -> B -> C (距離3)
* D -> E -> B -> A -> B -> E -> D (距離5)
* E -> B -> A -> B -> E (距離4)

このように、Dijkstraアルゴリズムは各頂点への最短距離と、その経路を正しく求めました。ステップ4で頂点Dへの距離がA->Dの経路（距離6）からA->B->E->Dの経路（距離5）に更新された点に注目してください。これが緩和処理の役割です。

5. Dijkstraアルゴリズムはなぜ正しく動作するのか？ 正当性の証明

Dijkstraアルゴリズムがなぜ非負の重みを持つグラフにおいて最短経路を正しく見つけられるのか、その正当性の証明は帰納法を用いて行うことができます。厳密な数学的証明は複雑になるため、ここではその核心となる考え方を分かりやすく説明します。

証明のアイデアは、「アルゴリズムがメインループで頂点uを取り出し、その距離dist[u]を確定させたとき、このdist[u]が始点sからuへの真の最短距離である」ことを示すことです。これがすべての頂点について言えれば、アルゴリズムの正しさが保証されます。

帰納法のステップ:

  1. 基底ケース: 最初のステップで、始点sがキューから取り出されます。このとき、dist[s]は0であり、これは明らかにsからsへの最短距離です。これは正しいです。

  2. 帰納的ステップ: あるステップで、アルゴリズムがキューから頂点uを取り出したと仮定します。このとき、dist[u]はキュー内の他のすべての頂点vのdist[v]の中で最小です。また、これまでにキューから取り出されたすべての頂点（確定済みの頂点）wについても、そのdist[w]は真の最短距離であると仮定します（帰納法の仮定）。この仮定の下で、今回取り出された頂点uのdist[u]も真の最短距離であることを示したいのです。

    背理法を用いて考えます。もしdist[u]が真の最短距離でないと仮定すると、始点sからuへの真の最短経路πが存在し、その長さはdist[u]よりも短いことになります。
    π: s = v₀ → v₁ → … → vk = u

    この真の最短経路πをたどっていくと、必ず初めて「まだキューに残っている頂点」が現れるはずです（u自身はキューから取り出されたばかりなので、それ以前にキューに残っていた頂点を必ず経由するはずです）。その頂点をviとします。つまり、v₀, v₁, …, vi-1はすでにキューから取り出されて確定済みであり、viはまだキューに残っている頂点です。vi-1は確定済みの頂点であり、viに直接つながっています。

    帰納法の仮定により、vi-1がキューから取り出された時点で、その距離dist[v<sub style="vertical-align: sub;">i-1</sub>]は真の最短距離でした。そして、アルゴリズムはvi-1を取り出した際に、viに対して緩和処理を行ったはずです。緩和処理により、dist[v<sub style="vertical-align: sub;">i</sub>]は dist[v<sub style="vertical-align: sub;">i-1</sub>] + w(v<sub style="vertical-align: sub;">i-1</sub>, v<sub style="vertical-align: sub;">i</sub>) と経路πの部分経路s → … → vi-1 → vi の長さのいずれか短い方に更新されています。
    真の最短経路πの部分経路もまた最短経路であるという「最適性の原理」により、sからviへの真の最短距離は、sからvi-1への真の最短距離に辺(vi-1, vi)の重みを加えたものと等しくなります。
    つまり、緩和処理の後、dist[v<sub style="vertical-align: sub;">i</sub>] はsからviへの真の最短距離以下になっているはずです。

    ここで重要なのは、viは真の最短経路π上の頂点であり、uよりも「始点sから見てπ上では手前にある（あるいはu自身である）」ということです。そして、辺の重みはすべて非負です。したがって、sからviまでの真の最短距離は、sからuまでの真の最短距離以下になります。
    真の shortest_dist(s, vi) ≤ shortest_dist(s, u)

    我々は当初、dist[u]が真の最短距離ではない、すなわち dist[u] > shortest_dist(s, u) であると仮定していました。
    また、緩和処理により、dist[v<sub style="vertical-align: sub;">i</sub>] ≤ shortest_dist(s, vi) となっています。

    これらの不等式を組み合わせると、
    dist[v<sub style="vertical-align: sub;">i</sub>] ≤ shortest_dist(s, vi) ≤ shortest_dist(s, u) < dist[u]

    つまり、dist[v<sub style="vertical-align: sub;">i</sub>] < dist[u] が導かれます。
    これは、頂点viがまだキューQに残っているにも関わらず、より距離の大きい頂点uがキューから取り出されたことになります。しかし、DijkstraアルゴリズムはキューQから常に最小距離の頂点を取り出すように設計されています。これは矛盾です。

    したがって、最初の仮定「dist[u]が真の最短距離でない」が誤りであったことになります。よって、アルゴリズムが頂点uを取り出したとき、dist[u]は真の最短距離であると言えます。

    この帰納的なステップは、すべての頂点がキューから取り出されるまで成り立ちます。最終的にすべての到達可能な頂点の最短距離が確定します。

負の重みが問題になる理由:

この証明の中で、「辺の重みはすべて非負」という性質が決定的に使われています。特に、真の最短経路π上でviがuよりも手前にあるならば、shortest_dist(s, vi) ≤ shortest_dist(s, u) が成り立つという部分です。もし負の重みを持つ辺が存在すると、最短経路は単純なパスであるとは限らず（サイクルを含む場合）、また、より多くの辺をたどることで全体のパスの重みが減少する可能性があります。この場合、始点sからviまでの最短距離が、sからuまでの最短距離よりも大きくなることがありえます。すると、上記のdist[v<sub style="vertical-align: sub;">i</sub>] < dist[u] という矛盾が導かれなくなり、アルゴリズムの正当性が崩れてしまいます。

負の重みを持つグラフでは、ベルマンフォードアルゴリズムのような別のアルゴリズムを使用する必要があります。

6. 計算量と効率

Dijkstraアルゴリズムの計算量は、グラフの表現方法（隣接リストか隣接行列か）と、優先度キューの実装方法によって大きく異なります。

グラフの表現方法:
* 隣接リスト: 各頂点に対して、それに隣接する頂点と辺の重みのリストを持つ方法です。辺の数が少ない疎なグラフ（EがV²に比べて非常に小さいグラフ）に適しています。
* 隣接行列: V×Vの行列で、要素(i, j)が頂点iから頂点jへの辺の重みを示す方法です。辺が存在しない場合は無限大などで示します。辺の数が多い密なグラフ（EがV²に近いグラフ）に適していますが、一般的には隣接リストの方が省メモリです。

優先度キューの実装方法:
優先度キューは、未訪問の頂点の中からdist値が最小のものを取り出すために使用されます。主な操作は以下の2つです。
* insert(vertex, priority): 頂点を優先度付きでキューに追加する。
* extract_min(): 最小優先度を持つ頂点を取り出す。
* decrease_key(vertex, new_priority): キュー内の頂点の優先度をより小さい値に更新する。

様々な実装方法とその計算量:

  1. 配列と線形探索: 優先度キューを単純な配列で表現し、extract_minを線形探索で行う場合。

    • 初期化: O(V)
    • メインループ: V回繰り返す。
      • extract_min: 未訪問の頂点すべて（最大V個）を探索するためO(V)。
      • 緩和処理: 各辺に対して最大1回行われる。合計E回の緩和処理が発生。緩和処理での距離更新自体はO(1)。
    • 全体の計算量: V × O(V) + E × O(1) = O(V²) + O(E) = O(V²).
    • 隣接リスト/行列どちらでも計算量は同じです。シンプルな実装ですが、グラフが大きい場合は非効率です。

  2. 二分ヒープ (Binary Heap): 優先度キューを二分ヒープで実装する場合。最も一般的な実装です。

    • 初期化: 全ての頂点をヒープに追加 O(V log V)。または、始点のみ追加し、緩和時に他の頂点を追加 O(V)。
    • メインループ: V回繰り返す。
      • extract_min: O(log V)
      • 緩和処理: 各辺(u, v)について、緩和が発生した場合に頂点vの優先度を更新（decrease_key）。二分ヒープでのdecrease_keyはO(log V)。緩和処理は合計E回発生する可能性がある。
    • 全体の計算量:
      • 隣接リストの場合: V × O(log V) + E × O(log V) = O((V+E) log V). V <= E+1 なので、これは O(E log V) と書かれることもあります。
      • 隣接行列の場合: 各頂点uについて、すべてのV個の頂点vに対して緩和を試みるため、緩和処理部分が V × O(V log V) となり、O(V² log V) になってしまいます。したがって、二分ヒープを使う場合は隣接リストが適しています。

  3. フィボナッチヒープ (Fibonacci Heap): 理論上最も効率的な優先度キューの実装方法。

    • 初期化: O(V)
    • メインループ: V回繰り返す。
      • extract_min: 償却計算量O(log V)。
      • 緩和処理 (decrease_key): 償却計算量O(1)。緩和は合計E回発生。
    • 全体の計算量: O(V log V + E).
    • これはDijkstraアルゴリズムの理論上の最良計算量ですが、フィボナッチヒープの実装は非常に複雑であり、定数倍の係数が大きいため、実用的には二分ヒープの方が高速なことが多いです。

まとめると:

  • 密なグラフ (E ≈ V²) の場合は、配列+線形探索の実装が O(V²) で、二分ヒープを使った O(V² log V) より効率的です。
  • 疎なグラフ (E << V²) の場合は、隣接リスト+二分ヒープの実装が O((E+V) log V) で、O(V²) よりはるかに効率的です。
  • 非常に大きなグラフで、理論上の限界を追求する場合は、隣接リスト+フィボナッチヒープが O(E + V log V) で最速となりますが、実装の複雑さから一般的ではありません。

ほとんどの現実世界のグラフ（道路網、インターネットなど）は疎であるため、Dijkstraアルゴリズムの実装としては「隣接リスト + 二分ヒープ」の組み合わせが最も一般的で実用的です。

7. Dijkstraアルゴリズムの制約と注意点

Dijkstraアルゴリズムは非常に強力ですが、適用できるグラフには重要な制約があります。

  • 負の重みを持つ辺が存在しないこと: これは前述の正当性の議論で触れた最も重要な制約です。辺の重みが負である場合、Dijkstraアルゴリズムは正しく最短経路を見つけることができません。負の重みを持つグラフ（ただし負の閉路は含まない）の単一始点最短経路問題には、ベルマンフォードアルゴリズムを使用する必要があります。負の閉路が存在する場合、最短経路は定義できません（無限に距離を短くできるため）。
  • グラフの種類: Dijkstraアルゴリズムは、有向グラフと無向グラフのどちらにも適用できます。無向グラフは、各無向辺を両方向への重みが等しい2つの有向辺として扱うことで容易に表現できます。

また、細かい点として、アルゴリズムの終了条件について触れておきます。すべての頂点が優先度キューから取り出されるまで続行するのが標準的ですが、特定の終点tへの最短経路だけを知りたい場合は、終点tがキューから取り出された時点でアルゴリズムを終了させても構いません。なぜなら、tが取り出された時点でその距離は確定しているからです。ただし、この最適化は計算量のオーダーを変えるほどの影響はありません。

到達不可能な頂点の扱いも重要です。始点から到達不可能な頂点のdist値は初期値の無限大のまま残ります。これは、そのような頂点への有限の長さの経路が存在しないことを正しく示しています。

8. 多様な応用分野

Dijkstraアルゴリズムは、そのシンプルさと効率性から、非常に幅広い分野で応用されています。

  • ナビゲーションシステム: 地図アプリやカーナビは、現在地から目的地までの最短経路（距離または時間）を計算するためにDijkstraアルゴリズム（またはその改良版であるA*アルゴリズム）をよく利用します。道路ネットワークをグラフとして表現し、道路の長さを重みとします。交通状況を考慮する場合は、通過時間を重みとして動的に変化させることもあります。
  • ネットワークルーティング: インターネットなどの通信ネットワークでは、データパケットを送信元から宛先まで効率的に転送する必要があります。OSPF (Open Shortest Path First) などのルーティングプロトコルは、ネットワーク内のルーター間の最短経路を計算するためにDijkstraアルゴリズムを使用します。回線の帯域幅や遅延を重みとします。
  • ゲームAI: ビデオゲームでキャラクターがマップ上を移動する際のパスファインディング（経路探索）によく使われます。マップをグリッドやノードグラフに分割し、Dijkstraアルゴリズムでキャラクターが障害物を避けつつ目的地までの最適な経路を見つけます。
  • 物流・配送最適化: 複数の地点を巡回するルート最適化問題（巡回セールスマン問題など）の部分問題として、あるいは倉庫から各配送先への最短経路を計算するためにDijkstraアルゴリズムが利用されます。
  • VLSI設計: 集積回路の配線において、信号の遅延を最小限に抑えるような経路を見つけるために使われることがあります。
  • 待ち行列理論: システムのスループットや遅延を分析する際に、状態遷移グラフ上の最短経路問題として定式化されることがあります。
  • 文字列処理: 編集距離（ある文字列を別の文字列に変換するために必要な最小限の操作回数）の計算など、様々な問題がグラフ問題に帰着され、Dijkstraアルゴリズムで解かれることがあります。

これらの例からわかるように、Dijkstraアルゴリズムは単なる理論的なアルゴリズムではなく、現代社会を支える様々なシステムの基盤技術として活躍しています。

9. 他の最短経路アルゴリズムとの比較

最短経路問題にはDijkstraアルゴリズム以外にも様々なアルゴリズムが存在します。それぞれの特性を理解することで、Dijkstraアルゴリズムの位置づけがより明確になります。

  • ベルマンフォードアルゴリズム (Bellman-Ford Algorithm):
    • 特徴: 負の重みを持つ辺が存在しても、負の閉路が含まれていなければ単一始点最短経路問題を解くことができます。負の閉路を検出する機能も持ちます。
    • 計算量: O(V * E)。
    • Dijkstraとの比較: Dijkstraより遅いですが、負の重みに対応できるという大きな利点があります。Dijkstraは貪欲に局所最適解を積み重ねますが、ベルマンフォードはすべての辺を何度も緩和することで大域的な最適解に近づいていきます。
  • A*アルゴリズム (A* Algorithm):
    • 特徴: Dijkstraアルゴリズムを改良したもので、単一始点-単一終点最短経路問題を解くために使われます。各頂点vに対して、終点までの推定距離（ヒューリスティック関数h(v)）を加算した値を優先度として利用します。このヒューリスティック関数が正確であるほど、目標地点に向かって探索を効率的にガイドできます。非負の重みを持つグラフで機能し、ヒューリスティック関数が単調性（consistent）を満たす場合、最短経路を見つけられます。
    • 計算量: 最悪ケースではDijkstraと同じですが、良いヒューリスティック関数があれば探索範囲を大幅に削減し、より高速に動作します。
    • Dijkstraとの比較: Dijkstraは始点から全方向へ均等に探索範囲を広げるのに対し、A*は終点への見込み距離を考慮して探索を終点方向へ「偏らせる」ことで効率化を図ります。特定の終点までの経路を見つけたい場合に有効です。
  • フローイド・ワーシャルアルゴリズム (Floyd-Warshall Algorithm):
    • 特徴: 全ての頂点ペア間の最短経路を計算するアルゴリズムです（全点対最短経路問題）。動的計画法を用いて解きます。負の重みを持つ辺が存在しても機能しますが、負の閉路が含まれている場合は最短経路は定義できません。
    • 計算量: O(V³)。
    • Dijkstraとの比較: Dijkstraは単一始点ですが、Floyd-Warshallは全点対です。もしすべての頂点ペア間の最短経路を知りたいのであれば、Dijkstraを各頂点を始点としてV回実行するよりも、密なグラフではFloyd-Warshallの方が効率的な場合があります（V回のDijkstraはO(V*(E+V)log V)）。疎なグラフではV回のDijkstraの方が速いことが多いです。Floyd-Warshallは実装が比較的シンプルです。

これらのアルゴリズムは、解決したい問題の種類（単一始点か全点対か）、グラフの特性（負の重みの有無）、必要な計算量などに応じて使い分けられます。Dijkstraアルゴリズムは、非負の重みを持つグラフでの単一始点最短経路問題という、非常に一般的かつ重要な問題に対して、効率的かつ正当な解を提供する基本的なアルゴリズムとして、その地位を確立しています。

10. 実装のヒント

Dijkstraアルゴリズムを実際にコードとして実装する際のヒントをいくつか紹介します。

  • グラフの表現: ほとんどのアプリケーションでは隣接リストが適しています。Pythonであれば辞書のリスト、C++であればstd::vector<std::vector<std::pair<int, int>>>のような形で表現できます（pairは{隣接頂点, 重み}）。
  • 優先度キュー: 多くのプログラミング言語の標準ライブラリには優先度キューの実装が含まれています（例: C++のstd::priority_queue、Javaのjava.util.PriorityQueue、Pythonのheapqモジュール）。これらを活用すると効率的な実装が可能です。標準ライブラリの優先度キューは、通常、最小値ではなく最大値を優先するヒープとして実装されていますが、要素の値を負にするか、あるいは(距離, 頂点)のタプルを入れて距離を優先度として扱うことで、最小値を優先する挙動を実現できます。
  • 距離の初期値: 無限大を表す値としては、言語の提供する最大値（例: float('inf') in Python, std::numeric_limits<double>::infinity() in C++, Double.POSITIVE_INFINITY in Java）か、あるいはグラフの辺の重みの合計よりも十分に大きい値を設定します。
  • 最短経路の再構築: prev配列（またはマップ）は、アルゴリズム終了後に終点から始点へ向かって先行頂点をたどることで、最短経路を逆順に得ることができます。これを反転させれば、始点から終点への経路が得られます。

例えばPythonで実装する場合の簡単な構造:

“`python
import heapq
import math

def dijkstra(graph, start_node):
distances = {node: math.inf for node in graph} # 距離の初期化
distances[start_node] = 0 # 始点の距離は0

# 優先度キュー (距離, ノード) のタプルを格納
# heapqは最小ヒープなので、距離をそのまま使う
priority_queue = [(0, start_node)]

predecessors = {node: None for node in graph} # 先行頂点の初期化

while priority_queue:
    current_distance, current_node = heapq.heappop(priority_queue)

    # すでに確定済みのより短い経路が見つかっている場合はスキップ
    # (これはheapqのdecrease_keyがないための工夫)
    if current_distance > distances[current_node]:
        continue

    # 隣接ノードを緩和
    if current_node in graph: # グラフにノードが存在するか確認
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 緩和処理
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

return distances, predecessors

グラフの例 (隣接リスト形式: {ノード: {隣接ノード: 重み}})

graph = {
‘A’: {‘B’: 2, ‘D’: 6},
‘B’: {‘A’: 2, ‘C’: 1, ‘E’: 2},
‘C’: {‘B’: 1},
‘D’: {‘A’: 6, ‘E’: 1},
‘E’: {‘B’: 2, ‘D’: 1}
} # 無向グラフを表現 (辺ABはA->BとB->Aで重み同じ)

始点をAとして実行

start_node = ‘A’
shortest_distances, path_predecessors = dijkstra(graph, start_node)

print(“Shortest Distances from”, start_node + “:”)
for node, dist in shortest_distances.items():
print(f”To {node}: {dist}”)

特定の終点までの経路を再構築する例

end_node = ‘C’
path = []
current = end_node
while current is not None:
path.append(current)
current = path_predecessors[current]
path.reverse()

print(“\nShortest Path from”, start_node, “to”, end_node + “:”)
print(” -> “.join(path))
“`

このPythonコードは、隣接リスト形式のグラフとheapqモジュールを使ったDijkstraアルゴリズムの基本的な実装を示しています。無向グラフの場合は、辺(u, v)があるときにリストにuからvへの辺とvからuへの辺の両方を追加する必要があります。

11. まとめ：Dijkstraアルゴリズムの重要性

Dijkstraアルゴリズムは、非負の重みを持つグラフにおける単一始点最短経路問題という、計算機科学および様々な工学分野における fundamental な問題に対する、効率的かつエレガントな解法です。その直感的な「最も近い未確定の頂点から確定していく」という考え方は、貪欲法の良い例であり、アルゴリズムの正当性も比較的容易に理解できます。

優先度キューを適切に利用することで、辺の数Eと頂点の数Vに対して O((E+V) log V) の計算量で動作し、特に現実世界で多く見られる疎なグラフに対して非常に効率的です。負の重みを持つ辺が存在するという制約はありますが、多くの現実世界の問題（距離、時間、コストなど）は非負であるため、Dijkstraアルゴリズムは広範な応用を持っています。

ナビゲーション、ネットワークルーティング、ゲームAIなど、私たちの身の回りにある多くの技術の基盤として、Dijkstraアルゴリズムとその考え方は不可欠です。このアルゴリズムを理解することは、グラフアルゴリズムの基礎を学び、より複雑な問題解決への足がかりを得る上で非常に重要です。

本記事を通じて、Dijkstraアルゴリズムの仕組み、動作例、正当性、計算量、そして応用について深く理解していただけたなら幸いです。この知識が、さらに進んだアルゴリズムやデータ構造の学習、あるいは現実世界の問題解決に役立つことを願っています。

コメントする

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

上部へスクロール