図解で理解！ダイクストラ法（最短経路探索）徹底解説

By /

図解で理解！ダイクストラ法（最短経路探索）徹底解説

はじめに：最短経路問題とダイクストラ法

私たちの日常生活は、最短経路を求める活動に満ち溢れています。スマートフォンで地図アプリを開けば、現在地から目的地までの最適なルートが瞬時に表示されます。カーナビゲーションシステム、電車の乗り換え案内、物流における配送ルートの決定、インターネット上でのデータパケットのルーティングなど、様々な場面で「 shortest path （最短経路）」を見つける問題が登場します。

このような最短経路問題は、コンピュータサイエンス、特にアルゴリズムの分野で古くから研究されてきました。そして、その中でも最も基本的ながら強力なアルゴリズムの一つが、「ダイクストラ法（Dijkstra’s algorithm）」です。

ダイクストラ法は、1959年にオランダの計算機科学者エドガー・ダイクストラによって考案されました。非負の重みを持つグラフにおける単一始点最短経路問題（ある一点から他の全ての点への最短経路を求める問題）を効率的に解くことができます。そのシンプルさと実用性の高さから、現在でも多くのシステムで利用されています。

この記事では、ダイクストラ法がどのように最短経路を見つけるのかを、図解をイメージしながらステップバイステップで徹底的に解説します。基本的な考え方からアルゴリズムの詳細、具体的な例題、計算量、応用例、そして注意点まで、このアルゴリズムの全てを網羅的に学んでいきましょう。この記事を読み終える頃には、ダイクストラ法の仕組みが手に取るように理解できているはずです。

さあ、最短経路探索の世界へ旅立ちましょう！

第1部：最短経路問題の基本 — グラフとは何か

ダイクストラ法を理解するためには、「グラフ」という概念を理解する必要があります。ここでいうグラフは、数学やコンピュータサイエンスにおけるグラフ理論のグラフであり、棒グラフや折れ線グラフとは異なります。

グラフは、ノード（Node, 頂点, Vertex）と、それらを結ぶエッジ（Edge, 辺）から構成される構造です。

  • ノード（頂点 V）: グラフにおける「点」や「場所」を表します。例えば、地図上の都市や交差点、コンピュータネットワークにおけるルーターなどがノードに対応します。
  • エッジ（辺 E）: ノードとノードを接続する「線」や「経路」を表します。地図上の道路や、ネットワークケーブルなどがエッジに対応します。

さらに、多くの場合、エッジには重み（Weight, コスト）が付けられています。これは、そのエッジを通るのにかかる時間、距離、費用などを数値で表したものです。最短経路問題では、この重みの合計が最も小さくなる経路を探します。

例えば、都市間の移動をグラフで考えると、都市がノード、都市を結ぶ道路がエッジ、そして道路の距離や移動時間がエッジの重みとなります。このグラフ上で、ある都市から別の都市への最短（最小重み合計）の経路を見つけることが、最短経路問題です。

グラフにはいくつかの種類がありますが、ダイクストラ法を考える上で重要なのは以下の点です。

  • 有向グラフと無向グラフ: エッジに方向があるかないかです。AからBへのエッジが必ずしもBからAへのエッジを意味しない場合（一方通行の道路など）は有向グラフ、どちらの方向にも移動できる場合は無向グラフと見なせます。ダイクストラ法はどちらにも適用可能ですが、有向エッジの場合はその方向にのみ移動できると考えます。
  • 重み: ダイクストラ法が正しく動作するためには、エッジの重みが全て非負であるという重要な制約があります。負の重みがあるグラフでは、ダイクストラ法は正しい結果を保証できません（これについては後述します）。

ダイクストラ法が解くのは、「単一始点最短経路問題（Single-Source Shortest Path, SSSP）」です。これは、「特定の開始ノードから、グラフ内の他の全てのノードへの最短経路」を求める問題です。

第2部：ダイクストラ法の基本的な考え方 — 貪欲なアルゴリズム

ダイクストラ法は、「貪欲法（Greedy Algorithm）」と呼ばれるアルゴリズムのカテゴリに属します。貪欲法は、その時点での最善の選択を繰り返し行うことで、全体としての最適な解を得ようとします。ダイクストラ法の場合、「まだ最短距離が確定していないノードの中で、現在最も開始ノードからの距離が小さいノードを次に探索する」という選択を繰り返します。

この「最も距離が小さいノード」を確定させていくプロセスが、ダイクストラ法の核心です。どのようにしてこれを実現するのでしょうか？

基本的なアイデアは以下の通りです。

  1. 開始ノードからの距離を記録する: 各ノードに対して、開始ノードからの現時点での最短距離の「推定値」を保持します。最初は開始ノード自身は距離0、他のノードは距離∞（無限大、まだ到達できないことを示す）とします。
  2. 距離の短いノードを確定する: まだ最短距離が確定していないノードの中から、現在の距離推定値が最も小さいノードを選び出します。このノードまでの距離は、これ以上短くならないことが保証されます（なぜなら、もしもっと短い経路があるなら、それはこのノードよりも先に「距離が短いノード」として選ばれているはずだからです。ただし、これは重みが非負である場合に限ります）。このノードの距離を「確定」とします。
  3. 隣接ノードの距離を更新（リラクセーション）する: 確定したノードから直接行ける（隣接する）ノードについて考えます。これらの隣接ノードへの距離が、「開始ノードから確定したノードまでの距離」＋「確定したノードから隣接ノードへのエッジの重み」よりも大きい場合、その隣接ノードまでの距離推定値をこの新しい値に更新します。これを「リラクセーション（Relaxation）」と呼びます。つまり、確定したノードを経由する経路の方が短い可能性があるなら、距離情報を改善するわけです。
  4. 繰り返し: 全てのノードの最短距離が確定するまで、ステップ2と3を繰り返します。

このプロセスを繰り返すことで、開始ノードから各ノードへの最短距離が徐々に明らかになり、最終的に全てのノードへの最短距離が求まります。

第3部：ダイクストラ法のアルゴリズム ステップ by ステップ (図解イメージ)

それでは、具体的なグラフを使って、ダイクストラ法のステップを追ってみましょう。ここでは、以下の要素を図で表現することをイメージしてください。

  • グラフ: ノード（丸）とエッジ（線）、エッジには重み（数値）が書かれています。
  • 距離テーブル: 各ノードについて、開始ノードからの現在の最短距離推定値を記録する表。
  • 訪問済みノード: 最短距離が確定したノード。色を変えるなどで区別します。
  • 未訪問ノード: まだ最短距離が確定していないノード。

例として、以下の無向グラフを考えます。

ノード：A, B, C, D, E, F
エッジと重み：
A-B: 7
A-C: 9
A-F: 14
B-C: 10
B-D: 15
C-D: 11
C-F: 2
D-E: 6
E-F: 9

開始ノードを A とします。

ステップ0：初期化

  • 各ノードへの最短距離推定値を初期化します。開始ノード A は距離 0。他のノード（B, C, D, E, F）はまだ到達していないので、距離を無限大 (∞) とします。
  • 最短距離が確定したノードの集合 visited を空とします。
  • まだ最短距離が確定していないノードの集合 unvisited に全てのノード {A, B, C, D, E, F} を追加します。

【図解イメージ】
* グラフが表示されています。
* 距離テーブル:
* A: 0
* B: ∞
* C: ∞
* D: ∞
* E: ∞
* F: ∞
* 全てのノードは未訪問（通常の色）。

ステップ1：未訪問ノードの中で、最も距離が小さいノードを選択

  • unvisited 集合 {A, B, C, D, E, F} の中で、距離テーブルの値が最も小さいノードを探します。
  • 現在の距離テーブルは A:0, B:∞, C:∞, D:∞, E:∞, F:∞ です。
  • 最も小さい距離は 0 で、対応するノードは A です。
  • A を次に探索するノードとして選択します。

【図解イメージ】
* 距離テーブルを再度表示。
* ノード A が「次に選択されるノード」として強調されています（例：太い枠線）。

ステップ2：選択したノードを訪問済みにし、未訪問集合から削除

  • 選択したノード A の最短距離が確定しました。
  • ノード A を visited 集合に追加します。 visited = {A}
  • ノード A を unvisited 集合から削除します。 unvisited = {B, C, D, E, F}

【図解イメージ】
* ノード A が「訪問済み」（確定済み）として色が変わります（例：青色）。
* 距離テーブルの A の距離 0 は確定値となります。

ステップ3：選択したノード（A）に隣接する未訪問ノードについて、距離を更新（リラクセーション）

  • ノード A に隣接するノードは B, C, F です。これらは全て unvisited 集合にいます。
  • 隣接ノード B:
    • A までの確定距離は 0 です。
    • A から B へのエッジの重みは 7 です。
    • A 経由で B への距離は 0 + 7 = 7 です。
    • 現在の B の距離は ∞ です。
    • min(∞, 7) = 7。 B の距離を 7 に更新します。
  • 隣接ノード C:
    • A までの確定距離は 0 です。
    • A から C へのエッジの重みは 9 です。
    • A 経由で C への距離は 0 + 9 = 9 です。
    • 現在の C の距離は ∞ です。
    • min(∞, 9) = 9。 C の距離を 9 に更新します。
  • 隣接ノード F:
    • A までの確定距離は 0 です。
    • A から F へのエッジの重みは 14 です。
    • A 経由で F への距離は 0 + 14 = 14 です。
    • 現在の F の距離は ∞ です。
    • min(∞, 14) = 14。 F の距離を 14 に更新します。

【図解イメージ】
* ノード A から B, C, F へのエッジが強調されます（例：点線）。
* 距離テーブルが更新されます:
* A: 0 (確定)
* B: 7
* C: 9
* D: ∞
* E: ∞
* F: 14
* 更新された距離が、該当するノードの横に書き込まれるイメージです。

ステップ4：全ノードが訪問済みになるまで繰り返す

まだ unvisited 集合は空ではありません。ステップ1に戻ります。

第2回目のループ

ステップ1：未訪問ノードの中で、最も距離が小さいノードを選択

  • unvisited 集合 {B, C, D, E, F} の中で、距離テーブルの値が最も小さいノードを探します。
  • 現在の距離テーブル (未確定部分): B:7, C:9, D:∞, E:∞, F:14 です。
  • 最も小さい距離は 7 で、対応するノードは B です。
  • B を次に探索するノードとして選択します。

【図解イメージ】
* 距離テーブルを再度表示。
* ノード B が「次に選択されるノード」として強調されます。

ステップ2：選択したノード（B）を訪問済みにし、未訪問集合から削除

  • ノード B の最短距離 7 が確定しました。
  • visited = {A, B}
  • unvisited = {C, D, E, F}

【図解イメージ】
* ノード B が「訪問済み」（確定済み）として色が変わります（例：青色）。

ステップ3：選択したノード（B）に隣接する未訪問ノードについて、距離を更新（リラクセーション）

  • ノード B に隣接するノードは A, C, D です。
  • 隣接ノード A は visited 集合にいるので無視します（最短距離は確定済みなので、A 経由で A に戻る経路は無意味です）。
  • 隣接ノード C:
    • B までの確定距離は 7 です。
    • B から C へのエッジの重みは 10 です。
    • B 経由で C への距離は 7 + 10 = 17 です。
    • 現在の C の距離は 9 です。
    • min(9, 17) = 9。 C の距離は 9 のまま更新されません（A 経由の方が短い）。
  • 隣接ノード D:
    • B までの確定距離は 7 です。
    • B から D へのエッジの重みは 15 です。
    • B 経由で D への距離は 7 + 15 = 22 です。
    • 現在の D の距離は ∞ です。
    • min(∞, 22) = 22。 D の距離を 22 に更新します。

【図解イメージ】
* ノード B から C, D へのエッジが強調されます。
* 距離テーブルが更新されます:
* A: 0 (確定)
* B: 7 (確定)
* C: 9
* D: 22
* E: ∞
* F: 14

ステップ4：全ノードが訪問済みになるまで繰り返す

まだ unvisited 集合 {C, D, E, F} は空ではありません。ステップ1に戻ります。

第3回目のループ

ステップ1：未訪問ノードの中で、最も距離が小さいノードを選択

  • unvisited 集合 {C, D, E, F} の中で、距離テーブルの値が最も小さいノードを探します。
  • 現在の距離テーブル (未確定部分): C:9, D:22, E:∞, F:14 です。
  • 最も小さい距離は 9 で、対応するノードは C です。
  • C を次に探索するノードとして選択します。

【図解イメージ】
* 距離テーブルを再度表示。
* ノード C が「次に選択されるノード」として強調されます。

ステップ2：選択したノード（C）を訪問済みにし、未訪問集合から削除

  • ノード C の最短距離 9 が確定しました。
  • visited = {A, B, C}
  • unvisited = {D, E, F}

【図解イメージ】
* ノード C が「訪問済み」（確定済み）として色が変わります。

ステップ3：選択したノード（C）に隣接する未訪問ノードについて、距離を更新（リラクセーション）

  • ノード C に隣接するノードは A, B, D, F です。
  • 隣接ノード A, B は visited 集合にいるので無視します。
  • 隣接ノード D:
    • C までの確定距離は 9 です。
    • C から D へのエッジの重みは 11 です。
    • C 経由で D への距離は 9 + 11 = 20 です。
    • 現在の D の距離は 22 です。
    • min(22, 20) = 20。 D の距離を 20 に更新します。
  • 隣接ノード F:
    • C までの確定距離は 9 です。
    • C から F へのエッジの重みは 2 です。
    • C 経由で F への距離は 9 + 2 = 11 です。
    • 現在の F の距離は 14 です。
    • min(14, 11) = 11。 F の距離を 11 に更新します。

【図解イメージ】
* ノード C から D, F へのエッジが強調されます。
* 距離テーブルが更新されます:
* A: 0 (確定)
* B: 7 (確定)
* C: 9 (確定)
* D: 20
* E: ∞
* F: 11

ステップ4：全ノードが訪問済みになるまで繰り返す

まだ unvisited 集合 {D, E, F} は空ではありません。ステップ1に戻ります。

第4回目のループ

ステップ1：未訪問ノードの中で、最も距離が小さいノードを選択

  • unvisited 集合 {D, E, F} の中で、距離テーブルの値が最も小さいノードを探します。
  • 現在の距離テーブル (未確定部分): D:20, E:∞, F:11 です。
  • 最も小さい距離は 11 で、対応するノードは F です。
  • F を次に探索するノードとして選択します。

【図解イメージ】
* 距離テーブルを再度表示。
* ノード F が「次に選択されるノード」として強調されます。

ステップ2：選択したノード（F）を訪問済みにし、未訪問集合から削除

  • ノード F の最短距離 11 が確定しました。
  • visited = {A, B, C, F}
  • unvisited = {D, E}

【図解イメージ】
* ノード F が「訪問済み」（確定済み）として色が変わります。

ステップ3：選択したノード（F）に隣接する未訪問ノードについて、距離を更新（リラクセーション）

  • ノード F に隣接するノードは A, C, E です。
  • 隣接ノード A, C は visited 集合にいるので無視します。
  • 隣接ノード E:
    • F までの確定距離は 11 です。
    • F から E へのエッジの重みは 9 です。
    • F 経由で E への距離は 11 + 9 = 20 です。
    • 現在の E の距離は ∞ です。
    • min(∞, 20) = 20。 E の距離を 20 に更新します。

【図解イメージ】
* ノード F から E へのエッジが強調されます。
* 距離テーブルが更新されます:
* A: 0 (確定)
* B: 7 (確定)
* C: 9 (確定)
* D: 20
* E: 20
* F: 11 (確定)

ステップ4：全ノードが訪問済みになるまで繰り返す

まだ unvisited 集合 {D, E} は空ではありません。ステップ1に戻ります。

第5回目のループ

ステップ1：未訪問ノードの中で、最も距離が小さいノードを選択

  • unvisited 集合 {D, E} の中で、距離テーブルの値が最も小さいノードを探します。
  • 現在の距離テーブル (未確定部分): D:20, E:20 です。
  • 最も小さい距離は 20 です。D と E のどちらを選んでも構いません。ここでは D を選びます。
  • D を次に探索するノードとして選択します。

【図解イメージ】
* 距離テーブルを再度表示。
* ノード D が「次に選択されるノード」として強調されます。

ステップ2：選択したノード（D）を訪問済みにし、未訪問集合から削除

  • ノード D の最短距離 20 が確定しました。
  • visited = {A, B, C, F, D}
  • unvisited = {E}

【図解イメージ】
* ノード D が「訪問済み」（確定済み）として色が変わります。

ステップ3：選択したノード（D）に隣接する未訪問ノードについて、距離を更新（リラクセーション）

  • ノード D に隣接するノードは B, C, E です。
  • 隣接ノード B, C は visited 集合にいるので無視します。
  • 隣接ノード E:
    • D までの確定距離は 20 です。
    • D から E へのエッジの重みは 6 です。
    • D 経由で E への距離は 20 + 6 = 26 です。
    • 現在の E の距離は 20 です。
    • min(20, 26) = 20。 E の距離は 20 のまま更新されません（F 経由の方が短い）。

【図解イメージ】
* ノード D から E へのエッジが強調されます。
* 距離テーブルは更新されません:
* A: 0 (確定)
* B: 7 (確定)
* C: 9 (確定)
* D: 20 (確定)
* E: 20
* F: 11 (確定)

ステップ4：全ノードが訪問済みになるまで繰り返す

まだ unvisited 集合 {E} は空ではありません。ステップ1に戻ります。

第6回目のループ

ステップ1：未訪問ノードの中で、最も距離が小さいノードを選択

  • unvisited 集合 {E} の中で、距離テーブルの値が最も小さいノードを探します。
  • 現在の距離テーブル (未確定部分): E:20 です。
  • 最も小さい距離は 20 で、対応するノードは E です。
  • E を次に探索するノードとして選択します。

【図解イメージ】
* 距離テーブルを再度表示。
* ノード E が「次に選択されるノード」として強調されます。

ステップ2：選択したノード（E）を訪問済みにし、未訪問集合から削除

  • ノード E の最短距離 20 が確定しました。
  • visited = {A, B, C, F, D, E}
  • unvisited = {}

【図解イメージ】
* ノード E が「訪問済み」（確定済み）として色が変わります。

ステップ3：選択したノード（E）に隣接する未訪問ノードについて、距離を更新（リラクセーション）

  • ノード E に隣接するノードは D, F です。
  • 隣接ノード D, F は visited 集合にいるので無視します。
  • 更新はありません。

【図解イメージ】
* 距離テーブルは最終確定値となります:
* A: 0 (確定)
* B: 7 (確定)
* C: 9 (確定)
* D: 20 (確定)
* E: 20 (確定)
* F: 11 (確定)

ステップ4：全ノードが訪問済みになるまで繰り返す

unvisited 集合が空になりました。アルゴリズムは終了です。

結果：最短距離

開始ノード A から各ノードへの最短距離は以下の通りです。

  • A → A: 0
  • A → B: 7
  • A → C: 9
  • A → D: 20
  • A → E: 20
  • A → F: 11

最短経路（パス）の復元

アルゴリズムの実行中に、各ノードの距離を更新する際に「どのノードを経由してその距離になったか」を一緒に記録しておくと、最短距離だけでなく、その経路自体も復元することができます。例えば、「parent」や「predecessor」ノードを記録する配列を用意します。

  • 初期化時：全ノードの parent を未定義とする。開始ノード A の parent は自分自身または未定義。
  • リラクセーション時：ノード v への距離を、ノード u を経由して更新した場合（dist[u] + weight(u, v) < dist[v]）、v の parent を u に設定する。

例：ノード E への最短距離 20 は F 経由 (距離 11 + 重み 9 = 20) で求まりました。このとき E の parent は F と記録します。
F への最短距離 11 は C 経由 (距離 9 + 重み 2 = 11) で求まりました。このとき F の parent は C と記録します。
C への最短距離 9 は A 経由 (距離 0 + 重み 9 = 9) で求まりました。このとき C の parent は A と記録します。

E の parent は F
F の parent は C
C の parent は A

したがって、E への最短経路は A → C → F → E と復元できます。経路の重み合計は 9 + 2 + 9 = 20 となり、求まった最短距離と一致します。

【図解イメージ】
* 最終的なグラフ上で、各ノードまでの最短経路を構成するエッジを太線や異なる色で表示します。
* 例えば、A→B (7), A→C (9), C→F (2), F→E (9), C→D (11), D→E (6) のエッジのうち、最短経路を構成するエッジ（A-B, A-C, C-F, C-D, F-E）などを強調し、確定した最短経路の「木構造」を描画します。

第4部：アルゴリズムの正当性 — なぜこれで最短が求まるのか？

ダイクストラ法が非負の重みを持つグラフで正しく最短経路を求めることができるのは、その貪欲な選択の性質と非負の重みという条件によるものです。

アルゴリズムの核心は、毎回未訪問ノードの中で「最も距離が小さいノード」を選び出し、その距離を確定させることです。なぜその距離が確定できるのでしょうか？

あるノード u を選択し、その距離 dist[u] を確定させたとします。u は、現時点の未訪問ノードの中で最も dist 値が小さいノードでした。もし、u への本当の最短経路が、まだ訪問されていない（最短距離が確定していない）他のノード v を経由するものであったと仮定します。

つまり、開始ノード S から v を経由して u へ行く経路 S → … → v → … → u が、S → … → u (現在の dist[u]) よりも短いとします。
この仮定が正しいならば、ノード v もまだ訪問されていない（unvisited 集合に入っている）はずです。

そして、非負の重みという条件があるため、S から v への最短経路の距離 dist[v] は、S から u への最短経路の距離 dist[u] より小さくなることはありません（少なくとも等しいか大きい）。なぜなら、もし dist[v] < dist[u] なら、u は dist[u] ではなく dist[v] がもっと小さいノードとして、u よりも前に選択されて距離が確定していたはずだからです。これは、u が未訪問ノードの中で最も距離が小さいノードとして選択されたという事実と矛盾します。

したがって、dist[v] >= dist[u] が成り立ちます。

S から v を経由して u へ行く経路の距離は、少なくとも dist[v] に v から u へのパスの重みを加えたものになります。このパスが直接のエッジ v → u であっても、間に他のノードを挟むとしても、非負の重みである限り、その経路の総重みは非負です。

仮に、S → … → v → u という経路が u への最短経路であり、dist[v] + weight(v, u) < dist[u] となったとします。もし v が u よりも前に確定していたなら、u の距離は v 経由で更新され、もっと小さくなっていたはずです。しかし、u が未訪問の中で最小として選ばれたということは、どの v も dist[v] >= dist[u] となっていたか、あるいは dist[v] + weight(v, u) が dist[u] よりも小さくならなかったかのどちらかです。

特に、u が選択された時点で、未訪問のどのノード v に対しても dist[v] >= dist[u] でした。そして、非負の重みなので、どのような未訪問ノード v と u の間の経路 v → … → u を考えても、その重みは 0 以上です。したがって、dist[v] + (v から u への経路の重み) >= dist[u] + 0 >= dist[u] となります。

つまり、一度 u の距離 dist[u] が未訪問ノードの中で最小として確定すると、開始ノード S から u への、まだ距離が確定していないノード（unvisited 集合のノード）を経由するどんな経路も、その総距離が dist[u] よりも短くなることはありません。

これが、ダイクストラ法が非負の重みにおいて正当である理由です。一度確定したノードへの距離は、それ以降更新されることはなく、それがそのノードへの最短距離となります。

第5部：計算量 — 効率的な実装のために

ダイクストラ法の効率は、未訪問ノードの中から最も距離が小さいノードをいかに素早く見つけ出すか、そしてリラクセーションの処理をいかに効率的に行うかに依存します。グラフの表現方法や使用するデータ構造によって、計算量が変化します。

グラフは一般的に、隣接行列（Adjacency Matrix）または隣接リスト（Adjacency List）で表現されます。

  • 隣接行列: V x V の行列で、要素 matrix[i][j] がノード i からノード j へのエッジの重みを表します。エッジがない場合は ∞ などで示します。ノード数 V が少ない場合に適しています。
  • 隣接リスト: 各ノードについて、それに隣接するノードと、そこへのエッジの重みをリストとして持ちます。エッジ数 E がノード数 V の2乗に比べて少ない疎なグラフに適しています。

ダイクストラ法の主要な操作は以下の2つです。

  1. 未訪問ノードの中から最小距離のノードを選択する。
  2. 選択したノードに隣接するノードの距離を更新する（リラクセーション）。

これらの操作をどのように実装するかで計算量が変わります。

1. 素朴な実装 (配列と線形探索)

未訪問ノードの集合を配列やリストで管理し、そこから最小距離のノードを探す際に線形探索を行う実装です。

  • 最小距離ノードの選択: 未訪問ノードが最大 V 個あるリストから最小値を見つけるのに O(V) かかります。これを V 回繰り返します。
  • リラクセーション: 選択したノードに隣接するノード全てについて行います。隣接リストを使えば、選択したノードに隣接するエッジの数 d (そのノードの次数) だけ処理が必要です。全てのリラクセーションの合計は、グラフのエッジ数 E に比例します（各エッジはリラクセーションに最大1回使われるため）。しかし、隣接リストの場合、各ノードの隣接ノードのリストをたどる処理は効率的です。

全体の計算量は、最小距離ノードの選択が V 回行われ、1回あたり O(V)かかるため O(V^2) となります。リラクセーションにかかる時間は、グラフ全体の構造によりますが、最大でも O(E)程度であり、O(V^2) が支配的です。したがって、素朴な実装の計算量は O(V^2) です。
隣接行列を使う場合も、隣接ノードを探すのに O(V) かかるため、同様に O(V^2) となります。

2. 優先度キュー (Priority Queue) を用いた実装

未訪問ノードとその距離を優先度キューで管理する実装です。優先度キューは、「最小要素の取り出し」と「要素の優先度（ここでは距離）の更新」を効率的に行うデータ構造です。二分ヒープなどが使われます。

  • 最小距離ノードの選択: 優先度キューから最小要素を取り出す操作で実現できます。ヒープを使った場合、これは O(log N) で可能です（Nはキュー内の要素数）。最大 V 個のノードがキューに入りうるため、O(log V) となります。これを V 回繰り返します。
  • リラクセーション: ノード u から隣接ノード v へのリラクセーションで dist[v] が更新される場合、優先度キュー内の v の優先度（距離）を変更する必要があります。この操作（Decrease Key）は、ヒープを使った場合 O(log N) で可能です。グラフ内の全てのエッジに対してリラクセーションが最大1回行われるため、全体で O(E log V) となります。

全体の計算量は、最小距離ノード選択にかかる時間 O(V log V) と、リラクセーションにかかる時間 O(E log V) の合計となり、O((E + V) log V) または O(E log V) (V << E の場合) となります。これは、特に疎なグラフ（E が V^2 に比べて小さいグラフ）においては、O(V^2) の素朴な実装よりも大幅に高速です。

さらに、理論上最も効率的なフィボナッチヒープを優先度キューとして使用すると、Decrease Key 操作が償却 O(1) となり、最小要素の取り出しが償却 O(log V) となります。この場合の計算量は O(E + V log V) です。ただし、フィボナッチヒープの実装は複雑であり、実用上は単純な二分ヒープやペアリングヒープなどがよく使われます。

空間計算量:

距離テーブル、parent 配列、訪問済みフラグなどのために O(V) の空間が必要です。隣接リストでグラフを表現する場合は O(V + E)、隣接行列の場合は O(V^2) の空間が必要です。優先度キューは最大で O(V) または O(E) の要素を持つため、追加の空間も考慮する必要がありますが、一般的には O(V + E) または O(V^2) が支配的です。

まとめると、計算量は以下のようになります。

実装方法 最小距離選択 リラクセーション 全体計算量
素朴 (配列+線形探索) O(V) x V = O(V^2) O(E) O(V^2)
優先度キュー (ヒープ) O(log V) x V = O(V log V) O(log V) x E = O(E log V) O((E + V) log V)
優先度キュー (フィボナッチ) O(log V) x V = O(V log V) O(1) x E = O(E) O(E + V log V)

実際の多くのグラフ、特に大規模なネットワークなどは疎であることが多いため、優先度キューを用いた実装が一般的に用いられます。

第6部：ダイクストラ法の応用例

ダイクストラ法は単一始点最短経路問題を解くための基本的なアルゴリズムであり、非常に多くの分野で応用されています。

  1. ナビゲーションシステム・地図アプリ:
    最も身近な応用例です。都市や交差点をノード、道路をエッジ、距離や推定移動時間を重みとするグラフ上で、現在地から目的地への最短経路（時間的または距離的）を計算します。渋滞情報などを考慮して重みを動的に変更することで、リアルタイムなナビゲーションが可能です。

  2. ネットワークルーティング:
    インターネットなどのコンピュータネットワークにおいて、データパケットがある地点から別の地点へ送られる際に、最も効率的な経路（遅延が最小、ホップ数が最小など）を選択するためにルーティングアルゴリズムが使われます。ダイクストラ法やその派生アルゴリズムは、ルーター間の接続をグラフと見なし、パケットの転送経路を決定するのに利用されます。OSPF (Open Shortest Path First) といったルーティングプロトコルは、リンクコスト（重み）に基づいて最短経路を計算する際に、ダイクストラ法の考え方に基づいています。

  3. 物流・配送最適化:
    複数の拠点や顧客間を巡回する際の最適な配送ルートを計算するために、ダイクストラ法が基本となります。ただし、複数の地点を特定の順序で回る巡回セールスマン問題のような複雑な問題はダイクストラ法だけでは解けませんが、ある地点から別の地点への最短移動時間/距離を計算する部分でダイクストラ法が利用されます。

  4. プロジェクト管理 (PERT図、クリティカルパス法):
    プロジェクトの各タスクをノード、タスク間の依存関係をエッジとし、タスクの所要時間を重みとするグラフを考えます。プロジェクト全体の完了に必須となる一連のタスク経路の中で、所要時間の合計が最も長くなる経路を「クリティカルパス」と呼びます。この最長経路（最大重みパス）を求める際に、エッジの重みを負にしてからダイクストラ法（またはベルマン・フォード法）を適用するという応用的な使い方がされることがあります（非負重みの場合は、重みを最大値から引くなどの工夫が必要）。

  5. ゲームAI:
    ゲームキャラクター（特に敵やNPC）がプレイヤーを追いかける際や、指定された場所に移動する際に、ゲーム内のマップをグラフと見なし、現在地から目的地への移動可能な最短経路を計算するために使用されます。経路探索アルゴリズムとしてはAアルゴリズムがよく使われますが、Aはダイクストラ法を拡張したものであり、ダイクストラ法の理解が基盤となります。

  6. その他:

    • 生物学: DNAやタンパク質の配列アライメントなど。
    • 金融: 最低コストで資産を変換する問題など。
    • 画像処理: 最短経路を画像上の特定の線として抽出するなど。

これらの応用例からもわかるように、ダイクストラ法は「ある始点から他の点への最小コストでの到達方法」を求めるという、非常に汎用的で重要な問題に対する効率的な解法を提供しています。

第7部：ダイクストラ法の注意点と限界 — 負の重み問題

ダイクストラ法には、その強力さの一方で、致命的な限界があります。それは、エッジの重みが負の場合には正しく動作しないという点です。

先述の正当性の説明で、「未訪問ノードの中で最も距離が小さいノードを選択する」際に、その距離が確定できる根拠として「非負の重みであること」が重要でした。つまり、「もし最短経路がまだ確定していないノード v を経由するなら、その経路長は現在確定しようとしているノード u までの距離以上になるはずだ」という前提が、非負の重みによって保証されていました。

しかし、負の重みエッジが存在すると、この前提が崩れてしまいます。

負の重みを持つエッジによる問題例:

グラフ：
ノード：A, B, C
エッジと重み：
A-B: 5
A-C: 10
C-B: -6

開始ノード A。
初期化：A:0, B:∞, C:∞

  1. 未訪問の中で最小距離：A (0) を選択、確定。visited={A}, unvisited={B, C}

  2. リラクセーション (Aから)：

    • A→B (5): dist[B] = min(∞, 0+5) = 5
    • A→C (10): dist[C] = min(∞, 0+10) = 10
      距離テーブル：A:0(確定), B:5, C:10

  3. 未訪問の中で最小距離：B (5) を選択、確定。visited={A, B}, unvisited={C}

  4. リラクセーション (Bから)：Bに隣接する未訪問はCのみ (無向グラフの場合)。

    • B→C (？): ここで問題。A→BでBが確定したが、実はA→C→Bの方が短い経路が存在するかもしれない。無向グラフの場合はC→Bエッジの両方向を考慮する。仮にここではC→B (-6) を考える。Cがまだ未確定なので、BからCへのリラクセーションは行わない。

  5. 未訪問の中で最小距離：C (10) を選択、確定。visited={A, B, C}, unvisited={}

  6. リラクセーション (Cから)：Cに隣接する未訪問は無い。

ダイクストラ法の終了時、AからBへの最短距離は 5 と求まってしまいます。
しかし、実際の最短経路は A → C → B (10 + (-6) = 4) であり、距離は 4 です。

ダイクストラ法は、一度ノードの距離を確定すると、それ以降は更新しません。この例では、A→B (5) でBの距離が5と確定してしまいましたが、後からより短い経路 A→C→B (4) が発見されたにも関わらず、Bの距離は更新されないため、間違った結果が出力されます。

負の閉路（Negative Cycle）

負の重みエッジが存在する場合、さらに深刻な問題として「負の閉路」が発生する可能性があります。負の閉路とは、エッジの重みの合計が負になる閉じた経路（サイクル）のことです。

例：A→B (2), B→C (3), C→A (-6)
このサイクルの重み合計は 2 + 3 + (-6) = -1 です。

このような負の閉路が存在すると、その閉路を何度も回ることで、いくらでも距離を小さくすることができてしまいます（例えば、Aから開始してA→B→C→A→B→C→A…と回ると、そのたびに経路の総重みが -1 ずつ減っていきます）。この場合、「最短経路」は定義できなくなります（無限に小さくなるため）。

ダイクストラ法は負の閉路を検出したり、正しく扱ったりすることはできません。

負の重みがある場合の対処法

負の重みを持つエッジ（ただし負の閉路は無い）が存在するグラフで最短経路を求める必要がある場合は、ベルマン・フォード法（Bellman-Ford algorithm）のような別のアルゴリズムを使用する必要があります。ベルマン・フォード法はダイクストラ法よりも計算量は大きいですが、負の重みエッジに対応しており、負の閉路も検出できます。

もし負の閉路が存在する場合は、多くの場合、最短経路問題そのものが「最短経路が存在しない」と判断され、エラーとなります。

第8部：他の最短経路アルゴリズムとの比較

最短経路問題を解くアルゴリズムは、ダイクストラ法以外にもいくつか存在します。問題の性質（重みの種類、始点の数など）に応じて、最適なアルゴリズムを選択する必要があります。

  1. 幅優先探索（BFS – Breadth-First Search）:

    • 適用条件: 重みのないグラフ（全ての重みが1または一定値と見なせる場合）。
    • 求める経路: 単一始点最短経路（エッジ数ベース）。
    • 計算量: O(V + E)。
    • 特徴: 重みがないグラフにおける最短経路探索としては最も効率的です。ダイクストラ法は重み付きグラフの最短経路探索ですが、重みがない場合はBFSと等価になります。

  2. ベルマン・フォード法（Bellman-Ford Algorithm）:

    • 適用条件: 負の重みを持つエッジが存在するグラフ（負の閉路は無い場合）。
    • 求める経路: 単一始点最短経路。
    • 計算量: O(V * E)。
    • 特徴: ダイクストラ法より遅いですが、負の重みに対応できます。負の閉路を検出する機能もあります。

  3. Floyd-Warshall法（フロイド・ウォーシャル法）:

    • 適用条件: 任意の実数の重みを持つグラフ（負の閉路は無い場合）。
    • 求める経路: 全点対最短経路（All-Pairs Shortest Path, APSP）、つまりグラフ内の全てのノードのペア間の最短経路。
    • 計算量: O(V^3)。
    • 特徴: 全てのペア間の最短経路を一度に求めることができます。負の重みにも対応しますが、負の閉路は検出できません（距離が無限に小さくなる可能性があります）。ダイクストラ法やベルマン・フォード法は単一始点ですが、Floyd-Warshall法は全点対です。

比較表:

アルゴリズム 適用できる重み 始点/終点 計算量 負の閉路対応
ダイクストラ法 非負の重みのみ 単一始点 O((E+V) log V) または O(E + V log V) ×
BFS 重みなし (= 全て1) 単一始点 O(V + E) 該当しない
ベルマン・フォード 負の重みを含む (負の閉路なし) 単一始点 O(V * E) ◯ (検出可能)
Floyd-Warshall 負の重みを含む (負の閉路なし) 全点対 O(V^3) ×

このように、問題の要件に合わせて適切なアルゴリズムを選択することが重要です。特に、負の重みの有無がダイクストラ法を選択できるかどうかの大きな分かれ目となります。

第9部：実装のヒント

ダイクストラ法を実際にプログラミング言語で実装する際のいくつかのヒントです。

  1. グラフ表現:
    ノード数 V が多くエッジが少ない疎なグラフでは、メモリ効率とリラクセーション時の隣接ノードへのアクセス効率から、隣接リストを使用するのが一般的です。配列のリストや、マップ（辞書）のリストなどで表現できます。

  2. 距離と親ノードの管理:
    各ノードへの最短距離を保持する配列（またはマップ）dist を用意します。初期値は開始ノードが0、他は無限大（浮動小数点数の infinity や、非常に大きな整数値）。
    最短経路を復元したい場合は、各ノードへの最短経路でその一つ手前となるノードを記録する配列 parent を用意します。

  3. 未訪問ノード集合と最小距離ノードの選択:
    これがパフォーマンスの鍵となります。

    • 素朴な方法: ブーリアン配列 visited で訪問済みかどうかを管理し、未訪問ノードの中から dist 値が最小のものを線形探索で探します。シンプルですが遅いです (O(V^2))。
    • 優先度キュー: 標準ライブラリで提供されている優先度キュー（例えばC++の std::priority_queue, Javaの PriorityQueue, Pythonの heapq など）を利用するのが最も現実的かつ効率的です。優先度キューには、(距離, ノード) のペアを格納し、距離を優先度として利用します。
      注意点として、多くの標準ライブラリの優先度キューは「最小要素の削除」は効率的ですが、「既存要素の優先度更新（Decrease Key）」は直接サポートしていないことが多いです。この場合、距離が更新されたノードを古い距離とともにキューに再挿入し、キューから要素を取り出す際に、既にもっと短い距離で確定済みのノードであれば無視する、という方法で対応します。これにより計算量は O(E log E) または O(E log V) となります（実際には E <= V^2 なので O(E log V) と見なせる）。

  4. 無限大の表現:
    到達不可能な距離を表す無限大には、言語のサポートする無限大値（例：Python float('inf')）を使うか、データ型の最大値よりも十分大きな値を定数として使うと良いでしょう。

  5. ループ条件:
    未訪問ノードの集合が空になるか、あるいは目的の終点ノードの距離が確定した時点でアルゴリズムを終了します。優先度キューを使う場合は、キューが空になるまで続行するのが標準的です。

擬似コード (優先度キュー使用)

“`
Dijkstra(Graph, start_node):
// 1. 初期化
dist = array of size V, initialized to infinity
dist[start_node] = 0
parent = array of size V, initialized to null

// 優先度キュー: (距離, ノード) のペアを格納
// 距離が小さい方が優先度が高い
priority_queue pq

pq.push((0, start_node)) // (距離, ノード)

// 2. メインループ
while pq is not empty:
// 未訪問の中で最も距離が小さいノードを取り出す
current_dist, current_node = pq.pop_min()

// より短い経路が既に見つかっていて、距離が更新されている場合は無視
if current_dist > dist[current_node]:
  continue

// current_node の距離が確定

// 3. 隣接ノードのリラクセーション
for each neighbor_node, weight in Graph.get_neighbors(current_node):
  distance_via_current = dist[current_node] + weight

  // より短い経路が見つかった場合
  if distance_via_current < dist[neighbor_node]:
    dist[neighbor_node] = distance_via_current
    parent[neighbor_node] = current_node // 経路復元用
    pq.push((distance_via_current, neighbor_node)) // 優先度キューに要素を追加/更新

// 4. 結果: dist[] に各ノードへの最短距離が格納される
// parent[] をたどることで最短経路を復元できる
return dist, parent
“`

この擬似コードは、標準ライブラリの優先度キューで Decrease Key が効率的に実装されていない場合に対応するため、距離が更新されたノードを再挿入する形式になっています。これにより、キューには同じノードに対して複数の距離が入る可能性がありますが、if current_dist > dist[current_node]: continue のチェックで、既に確定している（またはより短い距離でキューに登録済みの）ノードはスキップされます。

第10部：まとめ

この記事では、「図解で理解！」をテーマに、ダイクストラ法について徹底的に解説しました。

  • 最短経路問題とは何か、グラフの基本要素（ノード、エッジ、重み）を確認しました。
  • ダイクストラ法が非負の重みを持つグラフにおける単一始点最短経路問題を解くための、貪欲なアルゴリズムであることを理解しました。
  • アルゴリズムのステップバイステップの実行プロセスを、具体的な例題と距離テーブル、ノードの状態変化を追う図解イメージを通じて詳細にたどりました。初期化、最小距離ノードの選択、確定、リラクセーションというサイクルが、距離を確定していく仕組みであることを学びました。
  • なぜダイクストラ法が非負の重みで正しく動くのかという正当性の理由を考察しました。
  • 実装方法による計算量の違い（素朴なO(V^2)と、優先度キューを用いたO((E+V)logV)）を比較し、効率的な実装には優先度キューが不可欠であることを確認しました。
  • ナビゲーション、ネットワーク、物流など、様々な分野における豊富な応用例を知りました。
  • ダイクストラ法の最も重要な限界として、負の重みエッジに弱いこと、そして負の閉路には対応できないことを理解しました。負の重みがある場合はベルマン・フォード法などの他のアルゴリズムが必要となります。
  • 他の最短経路アルゴリズム（BFS, ベルマン・フォード法, Floyd-Warshall法）との比較を行い、問題の種類に応じたアルゴリズム選択の重要性を確認しました。
  • 最後に、実装のヒントとして、グラフ表現や優先度キューの使い方に触れました。

ダイクストラ法は、アルゴリズム学習において非常に重要かつ基本的なテーマです。そのシンプルながら強力なアイデアは、様々な最短経路問題に応用できる基盤となります。この記事を通じて、ダイクストラ法の仕組みとその力を深く理解していただけたなら幸いです。

shortest path の世界は奥深く、ダイクストラ法はその出発点に過ぎません。この記事で得た知識を足がかりに、さらに高度なアルゴリズムや複雑なグラフ問題へと学びを進めていくことを願っています。

これで、ダイクストラ法の徹底解説を終わりにします。最後までお読みいただき、ありがとうございました。

コメントする

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

上部へスクロール