これだけ読めば分かる！Dijkstra 算法の仕組みと使い方

By /

これだけ読めば分かる！Dijkstra 算法の仕組みと使い方

はじめに：最短経路問題とは何か？

私たちは日常生活の中で、「最短経路」という言葉をよく耳にします。例えば、スマートフォンで道案内アプリを使ったり、カーナビで目的地までの最適なルートを探したりする際に、無意識のうちに最短経路を計算しています。データ通信の世界でも、パケットがネットワーク上を流れる際に、効率的な経路を選択する必要があります。鉄道網や航空路線の計画においても、時間やコストを最小にする経路を見つけることは非常に重要です。

このように、ある場所から別の場所へ移動する際に、様々な制約（距離、時間、コストなど）を考慮して最も「良い」経路を見つける問題を「最短経路問題」と呼びます。ここで言う「良い」とは、通常、経路上の「重み」（辺に対応するコスト）の合計が最小になることを意味します。

最短経路問題にはいくつかの種類があります。
* 単一始点最短経路問題 (Single-Source Shortest Path, SSSP): グラフ内の特定の1つの頂点（始点）から、他のすべての頂点への最短経路を求める問題。
* 単一終点最短経路問題 (Single-Destination Shortest Path): グラフ内のすべての頂点から、特定の1つの頂点（終点）への最短経路を求める問題。これは、辺の向きを逆にして単一始点最短経路問題を解くことと同等です。
* 全ペア最短経路問題 (All-Pairs Shortest Path, APSP): グラフ内のすべての可能なペアの頂点間の最短経路を求める問題。

これらの問題の中でも、特に広く使われ、理解しやすいアルゴリズムの一つが「Dijkstra（ダイクストラ）算法」です。Dijkstra 算法は、グラフの辺の重みが非負である場合に、単一始点最短経路問題を効率的に解くための強力な手法です。この記事では、Dijkstra 算法がどのように機能するのか、その仕組みを徹底的に掘り下げ、具体的な使い方、計算量、そして限界について詳細に解説します。この記事を読めば、Dijkstra 算法の核心を理解し、様々な問題に応用できるようになるでしょう。

最短経路問題の基本を理解する

Dijkstra 算法を理解するためには、まずグラフ理論における基本的な概念を抑えておく必要があります。

グラフ (Graph)
グラフは、頂点（Vertex または Node）の集合 V と、それらの頂点間を結ぶ辺（Edge）の集合 E から構成されます。数学的には G = (V, E) と表記されます。

  • 頂点 (Vertex / Node): グラフにおける個々の要素（点）。都市、交差点、コンピュータネットワークの端末などが頂点として表現されます。
  • 辺 (Edge): 頂点間を結ぶ線。道路、通信ケーブル、フライト経路などが辺として表現されます。
    • 無向グラフ (Undirected Graph): 辺に向きがないグラフ。辺 {u, v} は u から v への移動と v から u への移動の両方を意味します。
    • 有向グラフ (Directed Graph): 辺に向きがあるグラフ。辺 (u, v) は u から v への一方的な移動を意味します。Dijkstra 算法は通常、有向グラフに対して説明されますが、無向グラフにも辺を両方向に持つ有向辺として表現することで適用可能です。

辺の重み (Weight)
多くの最短経路問題では、辺に関連付けられた「重み」があります。これは、その辺を通過するためにかかるコストを表します。重みは距離、時間、費用など、様々な物理量に対応します。重みを持つグラフを「重み付きグラフ (Weighted Graph)」と呼びます。通常、重みは実数で表されます。Dijkstra 算法が適用できるのは、この重みが非負である場合です。

経路 (Path)
経路とは、頂点のシーケンス v_0, v_1, …, v_k で、v_i と v_{i+1} の間に辺が存在するものです。始点 v_0 から終点 v_k への経路と呼びます。同じ頂点を複数回通る経路を「単純経路 (Simple Path)」ではないと言います。最短経路問題では、通常、単純経路が考慮されます（負の閉路がない限り、最短経路は常に単純経路となります）。

経路長 (Path Length)
経路 v_0, v_1, …, v_k の経路長は、その経路上のすべての辺の重みの合計です。
経路長 = w(v_0, v_1) + w(v_1, v_2) + … + w(v_{k-1}, v_k)
ここで w(u, v) は頂点 u から v への辺の重みを表します。

最短経路 (Shortest Path)
始点 s から終点 t への最短経路は、s から t へのすべての可能な経路の中で、経路長が最小となる経路です。

これらの基本的な概念を理解した上で、いよいよ Dijkstra 算法の核心に迫っていきましょう。

Dijkstra 算法の概要：貪欲なアプローチ

Dijkstra 算法は、オランダの計算機科学者エドガー・ダイクストラ（Edsger W. Dijkstra）によって1956年に考案され、1959年に発表されました。これは、単一始点最短経路問題を解くための非常に効率的なアルゴリズムとして、現代のコンピュータ科学において不可欠なツールの一つとなっています。

Dijkstra 算法の基本的な考え方は非常にシンプルです。これは「貪欲法 (Greedy Algorithm)」に基づいています。貪欲法とは、各ステップで局所的に最適な選択を行うことで、最終的に全体として最適な解を得ようとするアルゴリズム設計戦略です。Dijkstra 算法においては、「まだ最短距離が確定していない頂点の中から、現時点での始点からの距離が最も小さい頂点を選び、その頂点の最短距離を確定させる」というステップを繰り返します。そして、その確定した頂点を経由することで、まだ確定していない他の頂点への距離が短くならないかを確認し、必要に応じて距離を更新します。

このプロセスは、まるで水面に石を落としたときに波紋が広がる様子に例えられます。始点を中心に、距離が小さい頂点から順に最短距離が確定していき、まるで波紋のように外側へ広がっていくイメージです。

Dijkstra 算法の重要な制約は、辺の重みが非負である必要があるということです。この制約があるからこそ、「一度最短距離が確定した頂点は、その後さらに短い経路が見つかることはない」と保証できるのです。もし負の重みの辺が存在すると、確定したはずの頂点への最短経路が、負の辺を経由することで後からさらに短くなる可能性が出てきます。負の閉路（経路上の辺の重みの合計が負になる閉路）が存在する場合、経路長をいくらでも小さくできてしまうため、最短経路自体が定義できなくなります。

Dijkstra 算法の仕組み – 詳細解説

さて、Dijkstra 算法がどのように機能するのか、その詳細なメカニズムをステップバイステップで見ていきましょう。

Dijkstra 算法を実行するために、いくつかの情報を管理する必要があります。

  1. 距離配列 dist[]: 始点 s からグラフ内の各頂点 v への、現時点で見つかっている最短経路の距離を記録する配列です。最初は、始点 s への距離は 0、それ以外のすべての頂点への距離は「無限大」に初期化されます。無限大は、まだ到達可能な経路が見つかっていないことを意味します。
  2. 訪問済みセット visited[]: 始点からの最短距離がすでに「確定」した頂点の集合を管理します。通常はブール値の配列などで、各頂点が訪問済み（最短距離確定済み）かどうかを記録します。最初はすべての頂点が未訪問です。
  3. 優先度付きキュー (Priority Queue): これはアルゴリズムの効率性を高めるための重要なデータ構造です。まだ最短距離が確定していない頂点の中で、現時点での dist 値が最も小さい頂点を効率的に取り出すために使用します。キューには (距離, 頂点) のペアが格納され、距離を優先度として最小の要素が先頭に来るように管理されます。

それでは、アルゴリズムのステップを見ていきます。始点を start_node とします。

ステップ 1: 初期化

  • グラフ内のすべての頂点 v に対して、dist[v] を無限大に設定します。無限大は、実際にはコンピュータの表現可能な最大値や、特別なフラグ値などで表現されます。
  • 始点 start_node の距離を 0 に設定します: dist[start_node] = 0。
  • すべての頂点 v に対して、visited[v] を false に設定します。
  • 優先度付きキュー PQ を作成し、始点 (0, start_node) を挿入します。キューは (距離, 頂点) のペアを距離でソートします。

ステップ 2: メインループ

優先度付きキュー PQ が空になるまで、以下の処理を繰り返します。

a. 最小距離の頂点を取り出す: PQ から、最も距離が小さいペア (current_dist, u) を取り出します。これは、まだ最短距離が確定していない頂点の中で、始点からの距離が最も小さい頂点 u を見つける操作です。優先度付きキューを使うことで、この操作を効率的に行えます。
b. 訪問済みチェック: 取り出した頂点 u がすでに訪問済み（visited[u] が true）であれば、その頂点への最短距離はすでに確定しており、これ以上短い経路は見つからないため、この頂点の処理をスキップし、キューから次の頂点を取り出します。
c. 最短距離の確定: 取り出した頂点 u が未訪問であれば、dist[u] に格納されている距離 current_dist は、始点から u への最短距離であることが確定します。なぜなら、PQ から取り出されたということは、u へのすべての経路のうち、u を最後に訪問する経路の距離が current_dist であり、かつ u 以外の未訪問頂点への距離は current_dist 以上であるため、u へのこれ以上短い経路は存在しないからです（非負辺の性質がここで重要になります）。したがって、u を訪問済みとしてマークします: visited[u] = true。
d. 隣接頂点の距離更新 (緩和 – Relaxation): 頂点 u に隣接するすべての頂点 v について、以下の処理を行います。
* u から v への辺の重みを weight(u, v) とします。
* u を経由して v へ到達する新しい経路の距離を計算します: new_dist = dist[u] + weight(u, v)。
* もし、この新しい距離 new_dist が、現在記録されている dist[v] より小さい場合（つまり、dist[u] + weight(u, v) < dist[v]）、これは u を経由することで v へのより短い経路が見つかったことを意味します。
* この場合、v への距離を更新します: dist[v] = new_dist。
* そして、更新された距離 dist[v] とともに頂点 v を優先度付きキューに挿入します。もし v がすでにキュー内に存在し、その距離が更新された場合は、キュー内の v の優先度を更新する操作（decrease-key操作）が必要になりますが、多くの標準ライブラリの優先度付きキューでは、単に新しいエントリを挿入する（そして古いエントリは後で無視する）実装が用いられます。

ステップ 3: 結果

PQ が空になったとき、dist 配列には始点 start_node からグラフ内のすべての頂点への最短距離が格納されています。dist[v] が依然として無限大であれば、始点から頂点 v へは到達不可能であることを意味します。

なぜこの貪欲な選択でうまくいくのか？（非負辺の重要性）

Dijkstra 算法の核心は、「現時点で未確定の頂点の中で最も距離が小さいものを確定させる」という貪欲な選択が、全体最適（最短経路）に繋がるという点にあります。これが成り立つのは、辺の重みが非負であるという性質が鍵となります。

考えてみてください。PQから取り出された頂点 u は、未確定の頂点の中で dist[u] が最小です。もし、u へのさらに短い経路が存在すると仮定します。その経路は必ず、どこかで未訪問の頂点 w を経由しなければなりません（なぜなら、もしその経路上のすべての頂点が訪問済みなら、u も既に訪問済みとして取り出されているはずだからです）。その未訪問の頂点 w が u に到達する直前の頂点だとします。その経路長は dist[w] + weight(w, u) となります。

Dijkstra 算法が PQ から u を取り出した時点で、まだ未訪問の頂点 w の距離 dist[w] は、u への距離 dist[u] 以上であるはずです（なぜなら、u が未訪問頂点の中で最小距離として選ばれたからです）。
つまり、dist[w] >= dist[u] です。
辺の重み weight(w, u) は非負なので、weight(w, u) >= 0 です。
これらを合わせると、dist[w] + weight(w, u) >= dist[u] + 0 = dist[u] となります。
したがって、未訪問の頂点 w を経由する u への経路は、少なくとも dist[u] 以上の長さになります。これは、dist[u] よりも短い経路が u へ到達するために未訪問の頂点を経由することが不可能であることを意味します。

つまり、PQから取り出された頂点 u は、未訪問の頂点を経由してさらに短い経路で到達される可能性がないため、その距離 dist[u] は真の最短距離であると確定できるのです。この推論は、辺の重みが非負であることに強く依存しています。もし負の重みの辺 (w, u) が存在すれば、dist[w] + weight(w, u) が dist[u] よりも小さくなる可能性が出てしまい、この証明は成り立たなくなります。

Dijkstra 算法の実装

Dijkstra 算法を実際にプログラムとして実装する際には、グラフの表現方法と優先度付きキューの実装方法が重要になります。

グラフの表現方法

  • 隣接行列 (Adjacency Matrix): V 個の頂点を持つグラフは、V x V の行列で表現できます。行列 adj[i][j] の要素は、頂点 i から頂点 j への辺の重みを格納します。辺が存在しない場合は無限大などを格納します。頂点数が少ない密なグラフ（辺が多いグラフ）に適していますが、メモリ使用量が多くなります (O(V^2))。
  • 隣接リスト (Adjacency List): 各頂点に対して、それに隣接する頂点と辺の重みのリストを持つ方法です。例えば、頂点 i に隣接する頂点 j と辺の重み w は、リストに (j, w) のペアとして格納されます。頂点数が多く辺が少ない疎なグラフに適しています。メモリ使用量は O(V + E) となり、多くの現実世界のグラフではこちらが効率的です。

Dijkstra 算法の実装には、隣接リスト表現がよく使われます。

優先度付きキュー (Priority Queue) の実装

優先度付きキューは、以下の操作を効率的に行える必要があります。

  • 要素の挿入 (Insert)
  • 最小要素の取り出し (Extract-Min)
  • （必要に応じて）既存要素の優先度更新 (Decrease-Key)

標準的なデータ構造としては、二分ヒープ (Binary Heap) がよく用いられます。多くのプログラミング言語の標準ライブラリにヒープベースの優先度付きキューが用意されています（C++ の std::priority_queue、Java の PriorityQueue、Python の heapq モジュールなど）。ただし、標準ライブラリの優先度付きキューは通常 Decrease-Key 操作を直接サポートしていないため、距離が更新された頂点は新しい距離で再びキューに挿入されることが一般的です。古いエントリは、キューから取り出された際にすでに訪問済みであれば無視するという方法で処理します。

擬似コード

以下に、隣接リストと優先度付きキュー（二分ヒープを想定し、更新は新しい挿入で代用）を用いた Dijkstra 算法の擬似コードを示します。

“`pseudocode
Dijkstra(Graph G, Vertex start_node):
// G は隣接リスト形式で表現される（頂点 u から v への辺は u の隣接リストに (v, weight) として格納）
// V はグラフの頂点数
// E はグラフの辺数

// 1. 初期化
dist = array of size V, initialized to infinity for all vertices
dist[start_node] = 0

// visited = array of size V, initialized to false for all vertices
// （優先度付きキューと訪問済みチェックで代替するため、明示的な visited 配列は必須ではないが、
// 重複処理を防ぐために有効）

// Priority Queue stores pairs (distance, vertex)
// Ordered by distance (smallest first)
PQ = PriorityQueue()
PQ.insert((0, start_node))

// Optional: Predecessor array to reconstruct the path
// prev = array of size V, initialized to null
// prev[start_node] = start_node (or null, depending on convention)

// 2. メインループ
while PQ is not empty:
// a. 最小距離の頂点を取り出す
current_dist, u = PQ.extract_min()

// b. 訪問済みチェック（古いエントリを無視）
// if visited[u] is true: continue // If using explicit visited array
// If current_dist is greater than the already recorded dist[u],
// this is an old entry in the PQ due to distance updates. Ignore it.
if current_dist > dist[u]:
  continue

// c. 最短距離の確定 (implicit by processing)
// visited[u] = true // If using explicit visited array

// d. 隣接頂点の距離更新 (緩和)
for each neighbor v of u with edge weight w(u, v):
  new_dist = dist[u] + w(u, v)

  // もし u を経由する経路が v への現在の最短経路より短い場合
  if new_dist < dist[v]:
    dist[v] = new_dist
    // Optional: Record predecessor for path reconstruction
    // prev[v] = u
    PQ.insert((new_dist, v)) // 更新された距離で v をキューに追加

// 3. 結果
// dist array now contains the shortest distances from start_node
// return dist (and optionally prev)
“`

この擬似コードでは、明示的な visited 配列を使わずに、PQから取り出した要素の距離 current_dist が現在の dist[u] よりも大きい場合にスキップするという方法で、重複処理や古い距離による処理を防いでいます。これは、優先度付きキューが Decrease-Key 操作を効率的にサポートしない場合に一般的な実装テクニックです。PQ に同じ頂点の複数のエントリが入る可能性がありますが、extract_min は常に現在の最小距離のエントリを最初に取り出し、そのエントリが処理される際に dist[u] が確定（あるいは更新済みであると認識）されるため、古いエントリは current_dist > dist[u] の条件でスキップされます。

最短経路そのものを知りたい場合は、距離の更新を行う際に、どの頂点から来たか（前駆頂点）を記録する配列 prev を持つことで、アルゴリズム終了後に終点から始点へ prev を辿ることで経路を復元できます。

Dijkstra 算法の計算量

アルゴリズムの効率性は、その「計算量」（実行時間やメモリ使用量）によって評価されます。Dijkstra 算法の計算量は、使用するデータ構造、特に優先度付きキューの実装に依存します。グラフの頂点数を V、辺の数を E とします。

1. 素朴な実装 (優先度付きキューを使わない)

最も基本的な実装は、未訪問の頂点の中から距離が最小のものを線形探索で見つけ出す方法です。

  • 初期化: O(V)
  • メインループ: V 回繰り返されます（各頂点が1回だけ最短距離確定として取り出される）。
  • ループ内の処理:
    • 最小距離の未訪問頂点を見つける: 未訪問頂点のリスト（最大V個）から線形探索するため O(V)。
    • 隣接頂点の距離を更新: 頂点 u に隣接する辺の数 deg(u) だけ緩和操作を行います。
  • 合計計算量: 各頂点が1回取り出され、その際に最小距離の探索に O(V) かかります。緩和操作はすべての辺に対して合計2E回（無向グラフの場合）または E 回（有向グラフの場合）行われますが、各緩和操作自体は定数時間です。しかし、全体のボトルネックは最小距離の頂点を見つける部分で、これが V 回繰り返されるため、合計は O(V^2) となります。

この素朴な実装は、辺が多い密なグラフ (E ≈ V^2) に対しては比較的効率的ですが、辺が少ない疎なグラフ (E << V^2) に対しては非効率的です。

2. 二分ヒープ (Binary Heap) を使用した実装

前述の擬似コードのように、優先度付きキューとして二分ヒープを使用する場合、計算量は大幅に改善されます。

  • 初期化: O(V)
  • メインループ:
    • PQ から最小要素を取り出す (Extract-Min): ヒープのサイズは最大 V 個のエントリを持つため、O(log V)。この操作は最大 V 回行われます（各頂点が一度最短距離として取り出されるため）。
    • 隣接頂点の距離を更新 (緩和) し、PQ に挿入: 緩和操作自体は定数時間ですが、PQ への挿入 (Insert) は O(log V)。各辺 (u, v) に対して最大1回緩和操作が行われる可能性があります。したがって、挿入操作は合計で最大 E 回行われます。
  • 合計計算量: V回の Extract-Min 操作と最大 E 回の Insert 操作にかかる時間の合計は O(V log V + E log V) = O(E log V) となります（通常、連結グラフでは E >= V-1 であるため、E log V が支配的です）。

この実装は、特に疎なグラフにおいて O(V^2) の実装よりも格段に高速です。

3. フィボナッチヒープ (Fibonacci Heap) を使用した実装

理論的には、優先度付きキューとしてフィボナッチヒープを使用すると、計算量をさらに改善できます。フィボナッチヒープは、Extract-Min 操作は O(log V) ですが、Decrease-Key（距離更新）操作が償却解析で O(1) となります。Dijkstra 算法では、各辺の緩和に対応して Decrease-Key 操作が発生する可能性があるため、これが E 回行われることになります。

  • 初期化: O(V)
  • メインループ:
    • Extract-Min: V 回行われ、合計 O(V log V)。
    • Decrease-Key: 最大 E 回行われ、償却 O(E)。
  • 合計計算量: O(V log V + E)。

フィボナッチヒープは理論上は最も効率的ですが、実装が非常に複雑であり、定数倍の係数が大きいため、実用上は多くのケースで二分ヒープを用いた実装の方が高速であることが多いです。競技プログラミングや一部の特殊なアプリケーションを除き、一般的には二分ヒープを用いた O(E log V) 実装が使われます。

メモリ使用量については、隣接リストを使用した場合 O(V + E)、距離配列と訪問済み配列に O(V)、優先度付きキューに最大 O(V) または O(E)（実装による）かかるため、全体として O(V + E) となります。

Dijkstra 算法の注意点と限界

Dijkstra 算法は非常に強力ですが、万能ではありません。適用する際には以下の点に注意が必要です。

  1. 負の辺の重み: 前述したように、Dijkstra 算法は辺の重みが非負である場合にのみ正しく動作します。負の重みの辺が存在すると、一度最短距離が確定した頂点に対して、後から負の辺を経由することでより短い経路が見つかる可能性があり、アルゴリズムの根拠が崩れます。
  2. 負閉路: 負の閉路が存在する場合、その閉路を何度も周回することで経路長をいくらでも小さくできてしまうため、最短経路が定義できません（経路長がマイナスの無限大に向かう）。負の閉路が存在するかどうかを検出することも、最短経路問題においては重要な課題の一つです。
  3. 代替アルゴリズム: 負の辺が存在するグラフの単一始点最短経路問題を解くには、Bellman-Ford 算法や SPFA (Shortest Path Faster Algorithm) など別のアルゴリズムを使用する必要があります。これらのアルゴリズムは負の辺（および負閉路の検出）に対応できますが、Dijkstra 算法よりも計算量が大きくなります（Bellman-Ford は O(VE)）。全ペア最短経路問題で負辺がある場合は、Floyd-Warshall 算法 (O(V^3)) や、各頂点を始点として Bellman-Ford を実行する方法があります。

したがって、最短経路問題を解く際には、まずグラフに負の辺が存在するかどうかを確認することが重要です。非負辺であれば Dijkstra 算法が最速の選択肢の一つとなります。

Dijkstra 算法の応用例

Dijkstra 算法は、その効率性と有用性から、様々な分野で幅広く応用されています。

  • ナビゲーションシステム: カーナビや地図アプリは、現在地から目的地までの最短経路（通常は最短時間や最短距離）を計算するために Dijkstra 算法やその派生アルゴリズムを使用します。道路網をグラフとして捉え、交差点を頂点、道路を辺、所要時間や距離を辺の重みとして扱います。リアルタイムの交通情報（渋滞など）を重みに反映させることで、動的な最短経路探索も可能です。
  • ネットワークルーティング: インターネット上のパケット通信では、データを効率的に送信するために最適な経路を選択する必要があります。OSPF (Open Shortest Path First) のようなルーティングプロトコルは、ネットワークルーター間のリンクをグラフとして表現し、遅延や帯域幅などの指標を辺の重みとして、Dijkstra 算法を用いてルーティングテーブル（どの宛先へ向かうには次のルーターはどこか）を計算します。
  • 交通網の最適化: 鉄道会社や航空会社は、運行スケジュールの作成、遅延時の代替経路の計算、リソース（車両、乗務員）の効率的な割り当てなどに最短経路問題を応用します。駅や空港を頂点、路線やフライトを辺、所要時間やコストを重みとします。
  • リソース割り当てとスケジューリング: 生産計画、サプライチェーン管理、プロジェクト管理などにおいて、タスク間の依存関係やコスト、時間を考慮して最適な実行順序やリソースの割り当てを決定する際に、グラフモデルを用いた最短経路（または最長経路）問題として定式化し、Dijkstra 算法などが応用されることがあります。
  • ゲームAI: ビデオゲームやシミュレーションにおいて、キャラクターがマップ上で目的地までの移動経路を計算する際に Dijkstra 算法（あるいはA*探索など）が利用されます。マップ上の通行可能な場所をグリッドやノードとして表現し、移動コストを重みとします。
  • その他: 機械学習における特定のグラフ構造上での最適化、遺伝子配列の比較、画像処理など、グラフで表現できる多くの問題で最短経路アルゴリズムが基礎技術として使われています。

このように、Dijkstra 算法は単なる理論上のアルゴリズムではなく、私たちの身の回りの技術を支える重要な要素技術となっています。

具体的な例題とステップバイステップ解説

簡単なグラフを用いて、Dijkstra 算法がどのように動作するかを具体的に追ってみましょう。以下のグラフを考えます。頂点は A, B, C, D, E で、辺とその重みは図で示されています。始点を A とします。

(5) (2)
A ------> B ------> C
| \ | \ |
(1) | (3) | (4) | (6)
| \ | \ |
V \ V \ V
D ------> E <------ C
(2) (7)

これは有向グラフです。各辺の重みは非負です。

初期化:

  • dist 配列: dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞, dist[E]=∞
  • visited 配列: visited[A]=false, visited[B]=false, visited[C]=false, visited[D]=false, visited[E]=false
  • 優先度付きキュー PQ: {(0, A)}
  • prev 配列 (経路復元用): prev[A]=null, 他は null

ステップ 1:

  • PQ から最小距離の (0, A) を取り出す。current_dist=0, u=A。
  • current_dist (0) は dist[A] (0) と等しいので処理続行。
  • visited[A] を true に設定。
  • A に隣接する頂点 B と D を緩和。
    • 辺 A -> B (重み 5): new_dist = dist[A] + 5 = 0 + 5 = 5。dist[B] (∞) より小さいので更新: dist[B] = 5。PQ に (5, B) を挿入。prev[B] = A。
    • 辺 A -> D (重み 1): new_dist = dist[A] + 1 = 0 + 1 = 1。dist[D] (∞) より小さいので更新: dist[D] = 1。PQ に (1, D) を挿入。prev[D] = A。
  • PQ: {(1, D), (5, B)}

ステップ 2:

  • PQ から最小距離の (1, D) を取り出す。current_dist=1, u=D。
  • current_dist (1) は dist[D] (1) と等しいので処理続行。
  • visited[D] を true に設定。
  • D に隣接する頂点 E を緩和。
    • 辺 D -> E (重み 2): new_dist = dist[D] + 2 = 1 + 2 = 3。dist[E] (∞) より小さいので更新: dist[E] = 3。PQ に (3, E) を挿入。prev[E] = D。
  • PQ: {(3, E), (5, B)}

ステップ 3:

  • PQ から最小距離の (3, E) を取り出す。current_dist=3, u=E。
  • current_dist (3) は dist[E] (3) と等しいので処理続行。
  • visited[E] を true に設定。
  • E に隣接する頂点はない。
  • PQ: {(5, B)}

ステップ 4:

  • PQ から最小距離の (5, B) を取り出す。current_dist=5, u=B。
  • current_dist (5) は dist[B] (5) と等しいので処理続行。
  • visited[B] を true に設定。
  • B に隣接する頂点 C と E を緩和。
    • 辺 B -> C (重み 2): new_dist = dist[B] + 2 = 5 + 2 = 7。dist[C] (∞) より小さいので更新: dist[C] = 7。PQ に (7, C) を挿入。prev[C] = B。
    • 辺 B -> E (重み 4): new_dist = dist[B] + 4 = 5 + 4 = 9。dist[E] (3) より大きいので更新しない。
  • PQ: {(7, C)}

ステップ 5:

  • PQ から最小距離の (7, C) を取り出す。current_dist=7, u=C。
  • current_dist (7) は dist[C] (7) と等しいので処理続行。
  • visited[C] を true に設定。
  • C に隣接する頂点 C と E を緩和。（C->C は自己ループ、重み6）
    • 辺 C -> C (重み 6): new_dist = dist[C] + 6 = 7 + 6 = 13。dist[C] (7) より大きいので更新しない。
    • 辺 C -> E (重み 7): new_dist = dist[C] + 7 = 7 + 7 = 14。dist[E] (3) より大きいので更新しない。
  • PQ: {}

PQ が空になったのでアルゴリズム終了。

最終結果:

  • dist[A] = 0
  • dist[B] = 5 (経路: A -> B)
  • dist[C] = 7 (経路: A -> B -> C)
  • dist[D] = 1 (経路: A -> D)
  • dist[E] = 3 (経路: A -> D -> E)

経路復元:

prev 配列を使って、例えば A から C への最短経路を復元してみましょう。
終点 C から始めます。
* prev[C] = B → C の前に B がある。
* prev[B] = A → B の前に A がある。
* prev[A] = null → 始点に到達。

経路は A -> B -> C と復元できます。経路長は dist[C] = 7 で、これは辺の重みの合計 5 + 2 = 7 と一致します。

同様に A から E への経路は:
* prev[E] = D → E の前に D
* prev[D] = A → D の前に A
* prev[A] = null → 始点に到達。
経路は A -> D -> E と復元できます。経路長は dist[E] = 3 で、これは辺の重みの合計 1 + 2 = 3 と一致します。

この例からもわかるように、Dijkstra 算法は始点から距離の小さい順に頂点を確定させていき、その確定した頂点から「届く範囲」の他の頂点の距離を更新していくことで、効率的に最短距離を求めていることが分かります。

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

最短経路問題を解くアルゴリズムは Dijkstra 算法だけではありません。問題の種類やグラフの性質（特に辺の重み）に応じて、適切なアルゴリズムを選択する必要があります。

  • BFS (幅優先探索 – Breadth-First Search):

    • 特徴: 重みなしグラフの単一始点最短経路問題に適用できます。辺の重みがすべて1と等しいとみなせます。キューを使ってレベルごとに探索を進めます。
    • 計算量: O(V + E)
    • Dijkstra との違い: BFS は重みを考慮しません。Dijkstra は重みを考慮しますが、非負である必要があります。BFS は Dijkstra の辺の重みがすべて1である特殊ケースと考えることができます。

  • Bellman-Ford 算法:

    • 特徴: 負の辺の重みを持つグラフの単一始点最短経路問題を解くことができます。また、負閉路を検出することも可能です。動的計画法に基づいています。
    • 計算量: O(VE)
    • Dijkstra との違い: Bellman-Ford は負辺に対応できますが、Dijkstra より計算量が大きいです。Dijkstra は非負辺限定ですが、多くの場合 Bellman-Ford より高速です。

  • SPFA (Shortest Path Faster Algorithm):

    • 特徴: Bellman-Ford 算法の改善版で、負辺を持つグラフの単一始点最短経路に使われます。キューを用いて緩和操作を効率化しようとしますが、最悪ケースでは Bellman-Ford と同じ O(VE) になります。理論的な最悪計算量よりも実用上高速であることが多いですが、負閉路が存在する場合に無限ループになる可能性があるため注意が必要です。
    • 計算量: 最悪 O(VE)
    • Dijkstra との違い: SPFA は負辺に対応でき、Dijkstra より複雑で計算量も（最悪ケースで）大きいです。

  • Floyd-Warshall 算法:

    • 特徴: 全ペア最短経路問題を解きます。動的計画法に基づき、中間点として使用可能な頂点を徐々に増やしていくことで、すべてのペア間の最短距離を求めます。負の辺に対応できますが、負閉路が存在すると正しく機能しません（ただし、負閉路の存在を検出できます）。
    • 計算量: O(V^3)
    • Dijkstra との違い: Dijkstra は単一始点ですが、Floyd-Warshall は全ペアです。辺の重みが非負で全ペアを求めたい場合は、各頂点を始点として V 回 Dijkstra を実行する方が、疎なグラフでは Floyd-Warshall より効率的になることがあります (V * O(E log V))。

  • A 探索 (A Search):

    • 特徴: Dijkstra 算法を拡張したもので、特定の目標頂点への最短経路を効率的に探索します。ヒューリスティック関数を用いて、探索の方向を目標頂点の方へ誘導します。ゲームAIのパスファインディングなどでよく使われます。
    • 計算量: O(E) の辺を緩和する計算に加えて、ヒューリスティック関数の質に依存します。適切なヒューリスティック関数があれば、Dijkstra より高速に目標に到達できます。
    • Dijkstra との違い: A 探索は特定の終点への探索に特化しており、ヒューリスティック情報を利用することで探索範囲を絞り込むことができます。Dijkstra はすべての到達可能な頂点への最短距離を求めます。A は、正確なヒューリスティックを使用する場合、Dijkstra が探索する範囲よりも狭い範囲で解を見つけられます。

まとめると、辺の重みが非負の単一始点最短経路問題であれば、最も効率的で信頼性が高いアルゴリズムは Dijkstra 算法（特に優先度付きキューを用いた実装）です。負の辺がある場合は Bellman-Ford など他のアルゴリズムを検討する必要があります。

まとめ：Dijkstra 算法の要点

この記事では、「これだけ読めば分かる！」を目標に、Dijkstra 算法について詳細に解説してきました。その要点を改めてまとめておきましょう。

  • Dijkstra 算法は、単一始点最短経路問題を解くためのアルゴリズムです。
  • 適用できるグラフは、辺の重みがすべて非負である必要があります。負の重みや負閉路があるグラフには適用できません。
  • アルゴリズムの基本的な考え方は貪欲法です。「まだ最短距離が確定していない頂点の中で、現時点での距離が最も小さい頂点を順に取り出し、その頂点の最短距離を確定させる」というプロセスを繰り返します。
  • 効率的な実装には、優先度付きキューが不可欠です。これにより、未確定頂点の中から最小距離のものを素早く見つけ出すことができます。
  • 隣接リストと二分ヒープを用いた標準的な実装の計算量は O(E log V) です。
  • ナビゲーション、ネットワークルーティング、交通網の最適化など、幅広い分野で応用されています。
  • 負辺がある場合や全ペア shortest path など、問題の要件に応じて Bellman-Ford や Floyd-Warshall などの他のアルゴリズムを選択する必要があります。

Dijkstra 算法は、グラフアルゴリズムの基礎として非常に重要であり、多くの応用を持っています。その仕組みをしっかりと理解することで、様々な最適化問題を解決するツールとして活用できるでしょう。グラフ理論やアルゴリズムは奥深い分野ですが、Dijkstra 算法はその入り口として、仕組みと論理を学ぶのに最適です。

この記事が、あなたが Dijkstra 算法を理解し、使いこなすための一助となれば幸いです。さらに深く学びたい場合は、グラフアルゴリズムに関する専門書やオンラインコースを参照することをお勧めします。特に、様々なグラフ構造における実装の工夫や、A*探索のような派生アルゴリズムについても学ぶと、より多くの問題に対応できるようになるでしょう。

コメントする

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

上部へスクロール