最短経路探索の基本：ダイクストラ法のわかりやすい解説

By /

はい、承知いたしました。最短経路探索アルゴリズムの基本であるダイクストラ法について、約5000語の詳細でわかりやすい解説記事を作成します。

最短経路探索の基本：ダイクストラ法のわかりやすい解説

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

私たちの日常生活、そして現代社会のさまざまな場面で、「最短経路」を求めるという問題は非常に重要です。スマートフォンでカーナビアプリを使えば、出発地から目的地までの最適なルートが瞬時に表示されます。これはまさに最短経路を求めている典型的な例です。インターネット上では、データパケットがネットワーク内のルーターを経由して最短時間で目的地に到達するようにルーティングされています。ここでも最短経路の考え方が使われています。物流では、コストや時間を最小にするための配送ルートが計算されます。都市計画では、交通渋滞を緩和するための新しい道路や公共交通機関のルートが検討されます。これらすべてが、グラフ理論における「最短経路問題」として定式化され、アルゴリズムによって解決されています。

最短経路問題とは、グラフと呼ばれる点の集まり（頂点、ノード）とそれらを結ぶ線（辺、エッジ）からなる構造において、特定の開始点（始点）から特定の終了点（終点）まで、あるいは始点から他のすべての頂点まで、辺に定められた「重み（コスト）」の合計が最小となるような経路を見つけ出す問題です。この「重み」は、距離、時間、コストなど、状況に応じて様々な物理量や抽象的な値を表します。

この最短経路問題を解決するための最も基本的で広く知られているアルゴリズムの一つが、「ダイクストラ法（Dijkstra’s Algorithm）」です。1959年にエドガー・ダイクストラによって考案されたこのアルゴリズムは、単一始点最短経路問題（Single-Source Shortest Path problem）、つまり一つの特定の始点からグラフ内の他のすべての頂点への最短経路を求めるのに用いられます。特に、辺の重みが非負であるグラフに対して有効です。

本記事では、このダイクストラ法について、その基本的な考え方からアルゴリズムの詳細、具体的な実行例、さらにはその仕組みがなぜ正しく最短経路を導くのか、どのような場面で利用できるのかまでを、初心者の方にも分かりやすく、丁寧にかつ詳細に解説していきます。最終的には、ダイクストラ法がどのように機能し、どのような限界を持つのかを深く理解できるようになることを目指します。

グラフの基本要素と問題設定

ダイクストラ法を理解するためには、まずグラフの基本的な概念を整理しておく必要があります。

  • 頂点 (Vertex / Node): グラフにおける点のこと。都市、交差点、Webページなど、何かを表す対象物に対応します。
  • 辺 (Edge): 頂点と頂点を結ぶ線。道路、通信回線、リンクなど、頂点間の関係や接続を表します。
  • 重み (Weight): 辺に付けられた数値。距離、時間、コスト、容量などを表します。例えば、道路の長さ、通信にかかる時間、移動に必要な費用などです。
  • 経路 (Path): 頂点を順番にたどってできる辺の連なり。例えば、頂点AからB、BからCへと移動するなら、A-B-Cという経路になります。
  • 経路の重み: その経路を構成する辺の重みの合計。A-B間の重みがw1、B-C間の重みがw2なら、経路A-B-Cの重みはw1 + w2となります。
  • 最短経路 (Shortest Path): 複数の経路が存在する場合に、その中で経路の重みが最小となる経路のこと。

ダイクストラ法が解く問題は、具体的には以下のように定義されます。

  • 入力:
    • 有向グラフまたは無向グラフ G = (V, E)。Vは頂点の集合、Eは辺の集合です。
    • 各辺 e ∈ E に対する非負の重み w(e) ∈ ℝ⁺₀ (ℝ⁺₀は0以上の実数)。
    • 始点 s ∈ V。
  • 出力:
    • 始点 s からグラフ内の他のすべての頂点 v ∈ V への最短経路の重み（距離）。
    • （オプションとして）最短経路そのもの（どの頂点を経由したか）。

重要なのは、「辺の重みが非負である」という条件です。この条件があるからこそ、ダイクストラ法の greedy (貪欲) なアプローチが機能します。負の重みが許されるグラフでは、ダイクストラ法は正しく機能しません。その場合は、ベルマン・フォード法などの別のアルゴリズムが必要になります。

ダイクストラ法の基本的な考え方と直感的な説明

ダイクストラ法は、始点から近い頂点から順に、その頂点への最短距離を確定させていくという「貪欲（Greedy）」なアルゴロジーです。まるで、始点から水がじわじわと染み出し、重みが小さい（抵抗が少ない）辺を通って速く広がる様子に似ています。水が最初に到達した地点は、そこまでの最短距離が確定した場所と考えることができます。

より具体的に説明すると、ダイクストラ法は以下の二つの要素を管理しながら進行します。

  1. 確定済み集合 (Set of Finalized Vertices): 始点からの最短距離がすでに確定した頂点の集合。最初は始点のみが含まれます。
  2. 未確定集合 (Set of Unfinalized Vertices): まだ始点からの最短距離が確定していない頂点の集合。各未確定頂点に対しては、現在までに発見された最も短い経路による暫定的な距離が記録されています。

アルゴリズムは、以下の手順を繰り返します。

  1. すべての頂点への暫定的な距離を初期化します。始点への距離は0、それ以外の頂点への距離は無限大とします。（無限大は「まだ到達方法が見つかっていない」ことを意味します）。
  2. 始点を未確定集合に入れ、その暫定距離を0とします。
  3. 未確定集合が空になるまで、以下のステップを繰り返します。
    a. 未確定集合の中から、現在の暫定距離が最小である頂点 u を一つ選び出します。
    b. u を確定済み集合に移します。この時点での u の暫定距離が、始点からの最短距離であることが保証されます。
    c. 選び出した頂点 u に隣接するすべての未確定頂点 v について考えます。
    d. もし、「始点から u への最短距離」 + 「u から v への辺の重み」が、「現在記録されている v への暫定距離」よりも小さい場合、v の暫定距離をこの新しい値に更新します。これは「緩和（Relaxation）」と呼ばれる操作です。この更新は、「u を経由する方が、現在見つけている v へのどの経路よりも短い」ことを意味します。

このプロセスを続けることで、始点から「近い」頂点から順に最短距離が確定していきます。なぜ「暫定距離が最小である頂点」を選ぶことが重要なのでしょうか？ そして、なぜその頂点の距離が確定できるのでしょうか？

直感的に考えてみましょう。始点から未確定の頂点群の中で、最も暫定距離が小さい頂点 u を選びました。もし、u への真の最短経路が、まだ確定していない別の未確定頂点 v を経由すると仮定します。つまり、始点 -> … -> v -> … -> u という経路です。この経路の重みは、(始点からvまでの真の最短距離) + (辺v-uの重み) (+ もしあればvとuの間の他の辺の重み) となります。辺の重みはすべて非負なので、(始点からvまでの真の最短距離) は、(始点からuへの真の最短距離) よりも小さいか等しいはずです（uを経由せずにvに到達できるなら）。そして、未確定集合の中からuが選ばれたということは、uの暫定距離が、他のすべての未確定頂点の暫定距離（特にvの暫定距離）以下だったということです。

もし v 経由で u へのより短い経路が存在するなら、その経路上の最後の未確定頂点が u よりも前に選ばれるはずです。なぜなら、その頂点までの暫定距離は u までの暫定距離よりも小さいはずだからです（辺の重みは非負なので、パスに追加しても距離は減らない）。しかし、u が最小距離を持つ未確定頂点として選ばれたということは、このような v は存在しないということです。したがって、u が選ばれた時点でその暫定距離は最短距離であると確定できるのです。

この直感的な考え方を実現するために、アルゴリズムでは「未確定集合の中から暫定距離が最小の頂点を選び出す」操作を効率的に行う必要があります。ここで活躍するのが「優先度付きキュー (Priority Queue)」というデータ構造です。

ダイクストラ法の実装に必要なデータ構造

ダイクストラ法を効率的に実装するためには、いくつかのデータ構造が必要です。

  1. 距離配列 (Distance Array) / マップ: dist[v] のように、各頂点 v への始点からの現在の暫定距離を保持するための配列やマップです。初期値は始点 s に対しては dist[s] = 0、その他の頂点 v に対しては dist[v] = 無限大 となります。無限大は、まだ到達可能な経路が見つかっていないことを意味します。
  2. 先行頂点配列 (Predecessor Array) / マップ: prev[v] のように、各頂点 v への現在の最短経路において、v の直前に来る頂点を記録するための配列やマップです。これにより、アルゴリズム終了後に始点から各頂点への最短経路を逆順にたどって復元することができます。初期値は通常「未定義」などとします。
  3. 確定済み集合 (Set of Finalized Vertices) またはフラグ配列: 各頂点 v について、その最短距離がすでに確定したかどうかを記録するための集合や真偽値の配列/マップです。アルゴリズムのステップ3bで、未確定集合から取り出した頂点をここに移します。
  4. 未確定頂点の集合 / 優先度付きキュー (Priority Queue): ここが最も重要な部分です。未確定の頂点のうち、現在記録されている暫定距離が最小である頂点を効率的に取り出すために使用します。
    • 要素として、頂点とその時点での暫定距離のペア (距離, 頂点) を格納します。
    • 「挿入 (Insert)」操作：未確定の頂点とその暫定距離をキューに追加または更新します。
    • 「最小要素の取り出し (Extract-Min)」操作：キューの中から距離が最小であるペアを取り出します。
    • 「優先度の更新 (Decrease-Key)」操作：キュー内の要素の距離がより小さくなった場合に、その優先度を更新します。多くの標準的な優先度付きキューの実装では、この操作は明示的ではなく、「より良い距離で同じ頂点を再挿入する」という方法で模倣されることもあります。その場合、取り出し時にすでに確定済みの頂点であれば無視します。

優先度付きキューの実装方法によって、ダイクストラ法の実行効率が変わってきます。よく使われるのは二分ヒープ (Binary Heap) です。

ダイクストラ法のアルゴリズム詳細 (擬似コード付き)

上記を踏まえ、ダイクストラ法のアルゴリズムをより詳細に記述します。

入力:
* グラフ G = (V, E) (辺の重みは非負)
* 始点 s ∈ V

出力:
* 各頂点 v ∈ V への始点 s からの最短距離を格納した配列/マップ dist
* 各頂点 v ∈ V への最短経路において v の直前に来る頂点を格納した配列/マップ prev

アルゴリズム手順:

  1. 初期化:

    • 各頂点 v ∈ V に対して、距離 dist[v] を設定します。
      • もし v = s (始点) なら dist[s] = 0
      • それ以外の頂点 v ≠ s なら dist[v] = 無限大
    • 各頂点 v ∈ V に対して、先行頂点 prev[v] を「未定義」と設定します。
    • 処理すべき未確定頂点を入れる優先度付きキュー Q を作成します。
    • すべての頂点 v ∈ V を、その現在の暫定距離 dist[v] を優先度として Q に挿入します。最初は (0, s) と (無限大, v) (s以外のvについて) が入ります。
    • （あるいは、より一般的な実装では、最初 (0, s) のみ Q に入れ、発見時に Q に挿入/更新します。また、確定済みかを管理する集合/配列 visited を用意することもあります。）ここでは後者の、発見時にQに入れる（あるいは更新する）方式と、確定済みフラグを使う方式で説明を進めます。

    “`pseudocode
    // 距離と先行頂点を保持するマップ（または配列）
    dist := empty map
    prev := empty map
    visited := empty set // 最短距離が確定した頂点の集合

    // 優先度付きキュー：要素は (距離, 頂点) のペア
    Q := empty PriorityQueue

    // 初期化
    for each vertex v in V:
    dist[v] := infinity
    prev[v] := undefined

    dist[s] := 0
    Q.insert((0, s)) // 始点を距離0としてキューに追加
    “`

  2. 最短距離の確定と緩和 (Relaxation):

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

    “`pseudocode
    while Q is not empty:
    // Qから最もdist値が小さい頂点 u を取り出す
    (current_dist, u) := Q.extract_min()

    // すでにuへの最短距離が確定済み（処理済み）であればスキップ
if u in visited:
    continue

// uへの最短距離が確定したので、visitedに追加
visited.add(u)

// uに隣接する各頂点 v に対して緩和操作を行う
for each edge (u, v) in E:
    // 新しい経路 (s -> ... -> u -> v) の距離を計算
    new_dist := dist[u] + weight(u, v)

    // もし新しい経路の距離が、現在記録されている v への距離より小さければ更新
    if new_dist < dist[v]:
        dist[v] := new_dist // v への最短距離を更新
        prev[v] := u       // v の先行頂点を u に設定
        Q.insert((dist[v], v)) // Q に (新しい距離, v) を追加（あるいは更新）

    “`

  3. 結果:

    • while ループが終了した時点で、dist[v] には始点 s から各頂点 v への最短距離が格納されています。
    • prev[v] をたどることで、最短経路を復元できます。例えば、終点 t から prev[t]、prev[prev[t]]…と逆順にたどっていき、始点 s に到達するまでの頂点列が最短経路となります。

具体的な実行例

それでは、簡単なグラフを使ってダイクストラ法の実行ステップを追ってみましょう。

グラフ:

頂点: A, B, C, D, E
辺と重み（無向グラフと仮定）：
A – B: 3
A – C: 2
B – C: 1
B – D: 4
C – D: 2
C – E: 5
D – E: 2

始点: A

目標: 始点Aから他のすべての頂点への最短距離と最短経路を求める。

ステップ 処理概要 取り出した頂点 (u) current_dist 確定済み (visited) PQ (内容: (距離, 頂点)) dist[A] dist[B] dist[C] dist[D] dist[E] prev[B] prev[C] prev[D] prev[E]
初期化 すべての距離を∞、先行頂点を未定義に設定。始点Aの距離を0に設定し、PQに(0, A)を追加。 – – {} {(0, A)} 0 ∞ ∞ ∞ ∞ undef undef undef undef
1 PQから距離最小の(0, A)を取り出す。Aをvisitedに追加。Aに隣接するB, Cを緩和。 A 0 {A} {(2, C), (3, B)} 0 3 2 ∞ ∞ A A undef undef
– B: dist[A]+w(A,B)=0+3=3。distB>3 なので更新。dist[B]=3, prev[B]=A。Qに(3, B)追加。
– C: dist[A]+w(A,C)=0+2=2。distC>2 なので更新。dist[C]=2, prev[C]=A。Qに(2, C)追加。
2 PQから距離最小の(2, C)を取り出す。Cをvisitedに追加。Cに隣接するA, B, D, Eを緩和。 (Aはvisitedなのでスキップ) C 2 {A, C} {(3, B), (4, D), (7, E)} 0 3 2 4 7 A A C C
– B: dist[C]+w(C,B)=2+1=3。distB≦3 なので更新なし。（PQに(3, B)が残っているが、後で取り出された時にvisitedなのでスキップされるか、decrease-keyで更新されずに残る）
– D: dist[C]+w(C,D)=2+2=4。distD>4 なので更新。dist[D]=4, prev[D]=C。Qに(4, D)追加。
– E: dist[C]+w(C,E)=2+5=7。distE>7 なので更新。dist[E]=7, prev[E]=C。Qに(7, E)追加。
3 PQから距離最小の(3, B)を取り出す。Bをvisitedに追加。Bに隣接するA, C, Dを緩和。(A, Cはvisitedなのでスキップ) B 3 {A, C, B} {(4, D), (7, E)} 0 3 2 4 7 A A C C
– D: dist[B]+w(B,D)=3+4=7。distD≦7 なので更新なし。
4 PQから距離最小の(4, D)を取り出す。Dをvisitedに追加。Dに隣接するB, C, Eを緩和。(B, Cはvisitedなのでスキップ) D 4 {A, C, B, D} {(6, E), (7, E)} ※後で説明 0 3 2 4 6 A A C D
– E: dist[D]+w(D,E)=4+2=6。distE>6 なので更新。dist[E]=6, prev[E]=D。Qに(6, E)を追加。
5 PQから距離最小の(6, E)を取り出す。Eをvisitedに追加。Eに隣接するC, Dを緩和。(C, Dはvisitedなのでスキップ) E 6 {A, C, B, D, E} {(7, E)} ※後で説明 0 3 2 4 6 A A C D
6 PQから(7, E)を取り出す。Eはすでにvisitedなのでスキップ。PQが空になる。 E 7 {A, C, B, D, E} {} 0 3 2 4 6 A A C D

解説:

  • 初期化: 全頂点への距離は無限大（Aは0）。PQには(0, A)のみ。
  • ステップ1 (A): Aを取り出し確定。Aから行けるB(距離3), C(距離2)を緩和。dist[B]が3、dist[C]が2に更新。PQに(3, B), (2, C)が入る。
  • ステップ2 (C): PQから距離最小の(2, C)を取り出し確定。Cから行けるA(visited), B, D, Eを緩和。
    • Bへの距離は2+1=3。現在のdist[B]も3なので更新なし。
    • Dへの距離は2+2=4。dist[D]が4に更新、prev[D]=C。PQに(4, D)追加。
    • Eへの距離は2+5=7。dist[E]が7に更新、prev[E]=C。PQに(7, E)追加。
  • ステップ3 (B): PQから距離最小の(3, B)を取り出し確定。Bから行けるA(visited), C(visited), Dを緩和。
    • Dへの距離は3+4=7。現在のdist[D]は4なので更新なし。
  • ステップ4 (D): PQから距離最小の(4, D)を取り出し確定。Dから行けるB(visited), C(visited), Eを緩和。
    • Eへの距離は4+2=6。現在のdist[E]は7。6 < 7 なので更新。dist[E]が6に更新、prev[E]=D。PQに(6, E)を追加（またはPQ内の(7, E)を(6, E)に更新）。
    • 注: PQが「優先度の更新」をサポートしない実装の場合、(7, E)はPQ内に残ったままになります。ステップ5で(6, E)が取り出されvisitedに追加された後、ステップ6で(7, E)が取り出されますが、その時点でEはすでにvisitedなので無視されます。これが表のPQ内容の{(6, E), (7, E)}、{(7, E)}が示す挙動です。
  • ステップ5 (E): PQから距離最小の(6, E)を取り出し確定。Eから行けるC(visited), D(visited)を緩和（どちらもvisitedなのでスキップ）。
  • ステップ6 (E): PQから(7, E)を取り出すが、Eはすでにvisitedなのでスキップ。
  • PQが空になり、アルゴリズム終了。

結果:

始点Aからの最短距離:
dist[A] = 0
dist[B] = 3
dist[C] = 2
dist[D] = 4
dist[E] = 6

最短経路 (prevを逆順にたどる):
A -> B: A <- B (prev[B]=A)
A -> C: A <- C (prev[C]=A)
A -> D: A <- C <- D (prev[D]=C, prev[C]=A) -> A -> C -> D
A -> E: A <- C <- D <- E (prev[E]=D, prev[D]=C, prev[C]=A) -> A -> C -> D -> E

この例からも、ダイクストラ法が距離の短い頂点から順に確定していき、緩和操作によってより短い経路が発見されるたびに距離を更新していく様子がわかります。特にEへの経路は、最初A->C->E (距離7)が発見されますが、後からA->C->D->E (距離6)というより短い経路が発見され、距離が更新されています。

ダイクストラ法の正当性（なぜ動くのか）

ダイクストラ法が正しく最短経路距離を計算できるのは、辺の重みが非負であるという条件と、「優先度付きキューから取り出された頂点への距離が、その頂点への真の最短距離である」という性質に基づいています。

この性質をもう少し厳密に考えてみましょう。アルゴリズムが進行し、ある頂点 u が優先度付きキューから最小距離を持つものとして取り出されたとします。このとき、dist[u] が u への最短距離であると主張します。

もし dist[u] が最短距離ではないと仮定すると、u への真の最短経路は、u がキューから取り出される前に確定済み集合に入っていない、ある頂点 v を経由しなければなりません。つまり、最短経路は s -> … -> v -> … -> u のような形であり、かつ v は u が処理される時点では未確定集合に入っている必要があります。

辺の重みは非負なので、真の最短経路において、s から v までの距離は s から u までの距離以下になります（もし v が u より手前にあれば）。つまり dist_{true}(s, v) <= dist_{true}(s, u) です。

また、アルゴリズムの進行中に、v の暫定距離 dist[v] は常に dist_{true}(s, v) 以上です（発見されている経路は shortest ではないかもしれないが、辺の重みは非負なので、shortest 経路より短くなることはない）。

さて、u がキューから取り出されたということは、キューに残っている他のすべての未確定頂点 w に対して dist[u] <= dist[w] が成り立っています。特に、未確定頂点 v に対しても dist[u] <= dist[v] が成り立っています。

一方、仮定から真の最短経路は v を経由して u に到達するので、その経路の重みは dist_{true}(s, v) + (vからuへのパスの重み) となります。辺の重みが非負なので、vからuへのパスの重みは0以上です。

もし v 経由のパスが u への最短パスであるなら、それは u がキューから取り出される前に既に考慮されているはずです（少なくとも v の隣接頂点である u の緩和時に）。緩和操作によって dist[u] は可能な限り小さく更新されています。

矛盾が生じます。u が最小距離で取り出されたということは dist[u] <= dist[v] です。しかし、もし v を経由する真に短い経路が存在するなら、その経路上の最後の未確定頂点（多くの場合 v 自身、あるいは v と u の間にある未確定頂点）は u よりも真の最短距離が小さいはずであり、したがってその暫定距離も dist[u] より小さいか等しいはずです。すると、ダイクストラ法のルール（最小距離の未確定頂点を取り出す）により、u よりも先にその頂点が取り出されているべきです。これは u が最初に最小距離で取り出されたという事実に反します。

したがって、仮定は誤りであり、u がキューから取り出された時点での dist[u] は、u への真の最短距離でなければなりません。

この証明は、辺の重みが非負であるという条件が決定的に重要であることを示しています。もし負の重みを持つ辺が存在すると、既に確定したはずの頂点 u への最短経路が、後から発見された負の重みを持つ辺を経由することでさらに短くなってしまう可能性があります。ダイクストラ法は一度距離を確定するとその頂点を再訪しない（あるいは、より正確には優先度付きキューから取り出した時点でvisitedなら無視する）ため、このような負の辺による距離の短縮を捉えることができません。

計算量 (Time Complexity)

ダイクストラ法の計算量は、グラフの表現方法と優先度付きキューの実装方法に依存します。

グラフは通常、隣接リスト (Adjacency List) または隣接行列 (Adjacency Matrix) で表現されます。辺の数 E が頂点の数 V の二乗に比べて少ない（疎なグラフ）場合は隣接リストが効率的で、辺の数が多い（密なグラフ）場合は隣接行列が有利になることがあります。最短経路問題では、通常は隣接リストが使われます。

計算量の分析：

  1. 初期化: dist 配列、prev 配列の初期化、優先度付きキューへの全頂点の挿入。これは O(V) または O(V log V) かかります（PQへの挿入コストによる）。
  2. while ループ: 最大で V 回繰り返されます（各頂点が一度だけ確定済みになるため）。
  3. extract_min: 優先度付きキューから最小要素を取り出す操作。PQに格納されている要素数を N とすると、典型的なヒープ実装では O(log N) かかります。while ループの各反復で1回行われるため、合計 O(V log V) です。
  4. 緩和 (Relaxation): 各頂点 u が extract_min で取り出された後、その隣接頂点 v について緩和操作を行います。各辺 (u, v) について緩和操作が行われるのは最大1回です（u が extract_min された時にその辺を考慮するため）。したがって、緩和操作の合計回数は辺の数 E に比例します。各緩和操作では、dist の更新と優先度付きキューへの挿入/優先度更新が行われます。
    • 優先度付きキューに新しい要素を挿入する場合、O(log Q.size()) かかります。最悪の場合、QのサイズはVになります。合計 O(E log V)。
    • 優先度付きキュー内の要素の優先度を更新する場合（decrease-key）、これも典型的なヒープでは O(log V) かかります。合計 O(E log V)。

実装方法ごとの計算量:

  • ナイーブな実装 (優先度付きキューを使わず、未確定集合から線形探索):
    • extract_min に O(V) かかる。これを V 回行う。
    • 緩和は O(E) 回、各 O(1)。
    • 合計: O(V^2 + E) = O(V^2)。密なグラフ (E ≈ V^2) に適しています。
  • 二分ヒープ (Binary Heap) を使用した実装:
    • extract_min に O(log V) かかる。V 回で O(V log V)。
    • 緩和による挿入/更新に O(log V) かかる。E 回で O(E log V)。
    • 合計: O(V log V + E log V) = O((V + E) log V)。疎なグラフ (E << V^2) に適しており、これが最も一般的なダイクストラ法の計算量として知られています。
  • フィボナッチヒープ (Fibonacci Heap) を使用した実装:
    • extract_min の償却計算量が O(log V)。V 回で O(V log V)。
    • 緩和による挿入/優先度更新の償却計算量が O(1)。E 回で O(E)。
    • 合計: O(V log V + E)。理論上は二分ヒープより高速ですが、実装が複雑で定数倍のファクターが大きいため、実用上は二分ヒープが使われることが多いです。

まとめると、一般的に隣接リストと二分ヒープを組み合わせたダイクストラ法の計算量は O((V + E) log V) です。無向グラフの場合、各辺が隣接リストに二重に登録されるため E は無向辺の数の2倍になりますが、計算量のオーダーは変わりません。

ダイクストラ法の応用例

ダイクストラ法は、その基本的な性質（単一始点、非負重み）から、様々な現実世界の問題に応用されています。

  1. 経路探索システム:
    • カーナビゲーション: 地図上の交差点を頂点、道路を辺、道路の長さを重みとすることで、出発地から目的地までの最短距離経路を計算します。交通情報（渋滞など）を重みに反映させれば、最短時間経路を求めることも可能です（ただし、時間依存の重みの扱いは少し工夫が必要な場合があります）。
    • 公共交通機関のルート検索: 駅や停留所を頂点、路線区間を辺、乗車時間や乗り換え時間を重みとして、最小所要時間や最小乗り換え回数の経路を計算します。
  2. ネットワークルーティング:
    • インターネットやコンピュータネットワークにおいて、データパケットが送信元から宛先までを最短経路（ホップ数最小、遅延最小など）で到達するように、ルーターが経路を決定するプロトコル（例: OSPF (Open Shortest Path First), IS-IS (Intermediate System to Intermediate System)）の基礎となっています。重みはリンクの帯域幅、遅延、コストなどが用いられます。
  3. 物流・配送:
    • 配送センターや拠点を頂点、輸送ルートを辺、輸送コストや時間を重みとして、最適な配送ルートを計画します。
  4. ゲームAI:
    • ゲームキャラクターがマップ上で特定の地点まで移動する際の経路計算に利用されます。マップ上の地点を頂点、移動可能な通路を辺、移動コスト（地形、障害物など）を重みとします。
  5. その他の応用:
    • ロボットの経路計画
    • 画像処理（最小カット問題など）
    • バイオインフォマティクス（DNAシーケンスアライメントなど）
    • リソース割り当てやスケジューリング問題

これらの応用において、辺の重みが非負であるという前提が満たされていることが重要です。負の重みが出現する場合は、別のアルゴリズムを検討する必要があります。

ダイクストラ法と他の最短経路アルゴリズムとの比較

最短経路問題を解くアルゴリズムはダイクストラ法だけではありません。問題の特性（グラフの種類、重みの種類、始点/終点の数など）によって、より適切なアルゴリズムが存在します。

  1. 幅優先探索 (BFS):
    • 対象: 重みなしグラフ（またはすべての辺の重みが等しいグラフ）。
    • 方法: 始点から層状に探索を進め、距離が近い頂点から順に発見していく。キューを使用。
    • 計算量: O(V + E)。
    • 比較: ダイクストラ法はBFSの一般化とみなせます。辺の重みがすべて1の場合、ダイクストラ法はBFSと同じように動作し、計算量も同等になります（PQのオーバーヘッドはありますが）。重みがある場合は、BFSは最短経路を見つけられません。
  2. ベルマン・フォード法 (Bellman-Ford Algorithm):
    • 対象: 辺の重みが負であっても可（ただし、負の重みサイクルがないこと）。
    • 方法: すべての辺に対して繰り返し緩和操作を行い、各頂点への最短距離を更新していく。
    • 計算量: O(VE)。
    • 比較: ダイクストラ法より遅いですが、負の重み辺を扱える利点があります。負の重みサイクルを検出することもできます（負のサイクルがあると最短経路が定義できないため）。
  3. A 探索アルゴリズム (A Search Algorithm):
    • 対象: 非負の重みを持つグラフで、特定の始点から特定の終点への最短経路を効率的に見つけたい場合。ヒューリスティック関数が必要。
    • 方法: ダイクストラ法と同様に優先度付きキューを使用するが、キューの優先度を「始点からの暫定距離 + 終点までの推定距離（ヒューリスティック）」とする。
    • 計算量: 効率はヒューリスティック関数の質に大きく依存するが、うまく設計されたヒューリスティックを持つ場合、ダイクストラ法よりも探索範囲を限定できるため高速になることが多い。最悪の場合はダイクストラ法と同じ。
    • 比較: A*はダイクストラ法にヒューリスティクスを組み合わせたもので、単一始点から全点への最短経路ではなく、単一始点から単一終点への最短経路を目的とする場合に特に有効です。
  4. フロイド・ワーシャル法 (Floyd-Warshall Algorithm):
    • 対象: 辺の重みが負であっても可（ただし、負の重みサイクルがないこと）。すべての頂点ペア間の最短経路を求める。
    • 方法: 動的計画法を使用し、中間点として使用できる頂点の集合を徐々に増やしていく。
    • 計算量: O(V³)。
    • 比較: ダイクストラ法は単一始点問題、フロイド・ワーシャル法は全ペア問題に使用されます。全ペア問題をダイクストラ法で解くことも可能ですが（V回実行）、通常はフロイド・ワーシャル法の方がシンプルまたは効率的です（特に密なグラフで）。

このように、ダイクストラ法は「単一始点」かつ「非負重み」という条件のもとで、非常に効率的に機能するアルゴリズムとして位置づけられています。

ダイクストラ法の限界と注意点

ダイクストラ法の最も重要な限界は、繰り返しになりますが、辺の重みが非負でなければならないという点です。負の重みを持つ辺が存在する場合、ダイクストラ法は正しく最短経路を計算できません。これは、一度確定した頂点への距離が、後から発見された負の辺を経由する経路によってさらに短くなる可能性があるためです。

また、ダイクストラ法は単一の始点からの最短経路を求めます。もし「グラフ内のすべての頂点のペア間の最短経路」が必要な場合は、ダイクストラ法を各頂点を始点としてV回実行するか（非負重みなら可能）、あるいはフロイド・ワーシャル法のような全ペア最短経路アルゴリズムを使用する必要があります。

メモリ使用量についても触れておきましょう。標準的な隣接リスト表現の場合、グラフ自体の表現に O(V+E) のメモリが必要です。距離配列、先行頂点配列、visited 集合にそれぞれ O(V) が必要です。優先度付きキューには最悪 O(V) の要素が格納されるため、合計で O(V+E) の空間計算量となります。これは大規模なグラフでは無視できない量になる可能性があります。

まとめ：ダイクストラ法はなぜ基本なのか

ダイクストラ法は、辺の重みが非負であるという制約のもとで、単一始点最短経路問題を効率的に解くための最も基本的なアルゴリズムです。その「近い頂点から順に確定していく」という貪欲なアプローチは直感的であり、優先度付きキューを巧みに利用することで効率的な計算を実現しています。

その基本的な考え方、必要となるデータ構造、具体的な手順、そしてなぜそれが機能するのか（正当性）を理解することは、グラフアルゴリズム、特に経路探索アルゴリズムを学ぶ上で非常に重要です。多くの応用があり、またA*のような発展形アルゴリズムの基礎ともなっているからです。

ダイクストラ法の主要なポイント:

  • 目的: 単一の始点から他のすべての頂点への最短経路（の距離）を求める。
  • 前提: グラフの辺の重みは非負であること。
  • 基本的な考え方: 始点から近い未確定頂点から順に、その最短距離を確定していく。
  • 重要な要素:
    • 各頂点への現在の暫定最短距離を記録する (dist配列)。
    • 最短距離が確定した頂点を管理する (visited集合)。
    • 未確定の頂点の中で、暫定距離が最小のものを効率的に取り出すための優先度付きキュー。
  • 操作:
    • 初期化：始点距離0、他∞。
    • 緩和：隣接頂点へのより短い経路が見つかれば距離を更新。
    • 確定：優先度付きキューから取り出した頂点の距離を確定。
  • 計算量: O((V + E) log V) （二分ヒープ使用時）。
  • 限界: 負の重み辺は扱えない。

ダイクストラ法は、最短経路探索の分野における基礎であり、その概念は多くのアルゴリズムやシステムに応用されています。本記事を通じて、ダイクストラ法の「なぜ」と「どうやって」が明確になり、最短経路問題に対する理解が深まったことを願います。グラフアルゴリズムの世界は奥深く、ダイクストラ法はその魅力的な入口の一つと言えるでしょう。ぜひ、実際に簡単なグラフで手計算をしてみたり、プログラミングで実装してみたりして、その動きを体感してみてください。理論だけでなく、実際に動かしてみることで、アルゴリズムの理解は格段に深まります。

コメントする

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

上部へスクロール