はい、承知いたしました。「グラフの最短経路を見つけよう！ダイクストラ法の解説」というテーマで、約5000語の詳細な記事を直接ここに表示します。

グラフの最短経路を見つけよう！ダイクストラ法の解説

はじめに

現代社会において、私たちの生活は「つながり」によって成り立っています。インターネットの通信、交通網、物流システム、ソーシャルネットワーク、果ては脳の神経細胞のネットワークに至るまで、私たちの周りには「つながり」が溢れています。これらの「つながり」や「関係性」を表現する数学的なモデルが「グラフ」です。

グラフ理論は、このような構造を分析するための強力なツールであり、多くの現実世界の問題に応用されています。その中でも特に重要で広く知られている問題の一つが「最短経路問題」です。

最短経路問題とは、グラフ上の二つの点（頂点）の間を結ぶ経路のうち、最も「短い」経路を見つける問題です。ここでいう「短い」とは、単純に通過する辺の数が少ないという意味だけでなく、それぞれの辺に割り当てられた「重み」（コスト、距離、時間など）の合計が最小であるという意味で使われるのが一般的です。

例えば、カーナビゲーションシステムは、現在の位置から目的地までの最短時間または最短距離の経路を計算します。インターネット上でのデータの転送も、パケットがルーターを経由して最短の経路で届けられます。物流システムでは、配送センターから各店舗までの配送ルートを最適化する際に最短経路計算が用いられます。これらはすべて、グラフの最短経路問題を解くことで実現されています。

この最短経路問題を解くための最も有名で基本的なアルゴリズムの一つが「ダイクストラ法 (Dijkstra’s algorithm)」です。1959年にオランダの計算機科学者エドガー・ダイクストラによって考案されたこのアルゴリズムは、非負の辺の重みを持つグラフにおいて、一つの始点から他のすべての頂点への最短経路を効率的に見つけることができます。

この記事では、ダイクストラ法について、その仕組み、アルゴリズムの詳細なステップ、動作例、計算量、正当性、応用例、そして実装方法に至るまで、約5000語をかけて徹底的に解説します。この記事を読めば、ダイクストラ法がどのようにして最短経路を見つけるのか、その強力さと限界は何なのかを深く理解できるでしょう。

さあ、グラフの世界へ飛び込み、ダイクストラ法という素晴らしいアルゴリズムを探求していきましょう。

グラフの基本

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

グラフとは？

グラフは、頂点 (Vertex) の集合と、それらの頂点間を結ぶ辺 (Edge) の集合から構成される構造です。

頂点 (Vertex) / ノード (Node): グラフの構成要素となる点です。人、場所、都市、コンピュータなど、現実世界のオブジェクトやエンティティを表します。
辺 (Edge) / リンク (Link): 頂点と頂点を結ぶ線です。頂点間の関係、接続、経路などを表します。道路、通信回線、友人関係などが辺で表現できます。

グラフの種類

グラフにはいくつかの種類があり、解決したい問題に応じて適切なグラフモデルを選択します。

無向グラフ (Undirected Graph): 辺に方向がないグラフです。辺 (u, v) は、uからvへの接続とvからuへの接続の両方を意味します。例えば、ソーシャルネットワークにおける「友人」関係は、通常、無向グラフで表現されます（AがBの友人なら、BもAの友人）。
有向グラフ (Directed Graph) / ダイグラフ (Digraph): 辺に方向があるグラフです。辺 (u, v) は、uからvへの一方的な接続を意味します。vからuへの接続は、別途辺 (v, u) が存在しない限りありません。一方通行の道路や、ウェブサイトからのリンクなどは有向グラフで表現されます。
重み付きグラフ (Weighted Graph): 辺に「重み (Weight)」または「コスト (Cost)」と呼ばれる数値が割り当てられたグラフです。この重みは、辺の長さ、通過にかかる時間、コスト、容量など、その辺を通過することに関連する何らかの尺度を表します。道路の距離や、通信回線の遅延時間などが重みとして使われます。

ダイクストラ法は、主に重み付きグラフに適用されます。また、辺の重みは非負（0以上）である必要があります。有向グラフ、無向グラフのどちらにも適用できますが、無向グラフは各辺に対して両方向の有向辺を考えることで、有向グラフとして扱うことができます。

この記事では、特に断りがない限り、重み付き有向グラフを対象として説明を進めます。無向グラフの場合は、双方向の辺をそれぞれ有向辺としてモデル化すれば同様に扱えます。

グラフの表現方法

コンピュータ上でグラフを扱う際には、その構造を適切に表現する必要があります。主な方法としては以下の二つがあります。

隣接行列 (Adjacency Matrix): V個の頂点を持つグラフの場合、V x V の行列Aで表現します。A[i][j]の値は、頂点iから頂点jへの辺の存在とその重みを示します。辺が存在しない場合は、∞（無限大）や特定の大きな値で表します。
- メリット: 辺の存在判定や重みの参照がO(1)で高速。
- デメリット: 頂点数の2乗に比例するメモリが必要（疎なグラフでは無駄が多い）。辺の列挙に時間がかかる。
隣接リスト (Adjacency List): 各頂点vに対して、vから出る辺のリスト（または隣接する頂点のリスト）を保持します。リストには、接続先の頂点と辺の重みを記録します。
- メリット: 辺の数Eと頂点数Vに比例したメモリで済む（疎なグラフに有利）。特定の頂点から出る辺の列挙が容易。
- デメリット: 辺の存在判定や重みの参照にリストの探索が必要になる（リストがソートされていれば少し高速化可能）。

多くの現実世界のグラフ、特に大規模なグラフは疎であることが多いため、ダイクストラ法の実装には隣接リストが使われることが一般的です。この記事の実装例でも隣接リストを前提とします。

最短経路問題の定義

ダイクストラ法が解決するのは、「単一始点最短経路問題 (Single-Source Shortest Path Problem)」と呼ばれる問題です。

問題:
与えられた重み付きグラフ G=(V, E) と、Vに属する特定の始点 (Source Vertex) sに対し、sからグラフ内の他のすべての頂点 v ∈ V への最短経路（重みの合計が最小となる経路）を見つけ、その経路の重みの合計である最短距離を求めよ。

ここでいう「経路」とは、頂点の列 (v0, v1, …, vk) であり、v0=sであり、各 (vi, vi+1) がグラフの辺であるものです。経路の重みは、その経路上のすべての辺の重みの合計です。

ダイクストラ法が適用できるのは、すべての辺の重みが非負（≥ 0）である場合に限られます。辺の重みに負の値が含まれる場合、後述するようなダイクストラ法の基本的な仮定が崩れてしまい、正しく動作しません。負の重みを持つグラフの最短経路問題には、ベルマン・フォード法のような別のアルゴリズムが用いられます。

ダイクストラ法の核心

ダイクストラ法の基本的なアイデアは、始点sから近い頂点から順番に、その頂点までの最短距離を確定させていく、というものです。この方法は、パンを焼くときに中心部から徐々に熱が伝わっていく様子や、池に石を投げ入れたときに波紋が広がっていく様子に似ています。

アルゴリズムは、各頂点に対して「暫定的な最短距離」を保持します。最初は始点以外への距離はすべて無限大としておき、アルゴリズムが進むにつれて、より短い経路が見つかるたびにこの暫定距離を更新していきます。

アルゴリズムの核となる考え方は以下の通りです：

初期化: 始点sの暫定距離を0とし、他のすべての頂点の暫定距離を無限大とします。また、どの頂点もまだ「確定」していません。
最小距離の頂点の選択: まだ最短距離が確定していない頂点の集合の中から、現在の暫定距離が最も小さい頂点uを選びます。
確定: 選ばれた頂点uまでの暫定距離は、これ以上短縮されることはありません。なぜなら、もしuまでにもっと短い経路が存在するとすれば、その経路上のuの直前の頂点は、uよりも距離が小さいはずであり、それはuが「暫定距離が最小の未確定頂点」として選ばれたという事実と矛盾するからです（辺の重みが非負である限り）。したがって、uまでの暫定距離は確定し、これがsからuへの最短距離となります。
距離の更新 (リラクゼーション): 確定した頂点uから直接到達できる、まだ最短距離が確定していないすべての頂点vについて考えます。sからuへの最短経路を経由してvに到達する経路の距離（sからuまでの最短距離 + uからvへの辺の重み）を計算し、現在vに設定されている暫定距離と比較します。もし、計算した新しい距離の方が短い場合は、vの暫定距離を更新します。この操作を「リラクゼーション (Relaxation)」と呼びます。
繰り返し: 2～4のステップを、すべての頂点までの最短距離が確定するまで、または特定の目的の頂点までの最短距離が確定するまで繰り返します。

この「暫定距離が最小の未確定頂点を選んで確定させ、隣接頂点の距離を更新する」というプロセスを繰り返すことで、始点から近い順に最短距離が確定していくわけです。

ダイクストラ法のアルゴリズム (ステップバイステップ)

ダイクストラ法のアルゴリズムを、より具体的なステップで記述します。

入力:
* 重み付き有向グラフ G = (V, E)
* 辺の重み関数 w: E → [0, ∞) （すべての重みは非負）
* 始点 s ∈ V

出力:
* 各頂点 v ∈ V に対する、sからvへの最短距離 d[v]
* 必要であれば、最短経路を復元するための情報（例えば、各頂点vへの最短経路で、vの直前に位置する頂点 π[v]）

データ構造:
* d[v] (または dist[v]): 始点sから頂点vへの暫定的な最短距離を格納する配列またはマップ。
* π[v] (または prev[v]): 始点sから頂点vへの最短経路において、vの直前の頂点を格納する配列またはマップ。経路復元に使用。
* Q: まだ最短距離が確定していない頂点の集合。最初はすべての頂点を含む。アルゴリズムが進むにつれて、最短距離が確定した頂点はここから取り除かれる。

アルゴリズム手順:

初期化:
- グラフ内のすべての頂点 v ∈ V に対して、
  - d[v] = ∞ （無限大）。これは、最初はどの頂点への経路も知らないことを意味します。
  - π[v] = NIL （またはnull）。これは、最短経路上の直前の頂点がまだ不明であることを意味します。
- 始点 s に対して、d[s] = 0。始点から自分自身への距離は0です。
- Q を初期化し、すべての頂点 v ∈ V を Q に追加します。
メインループ:
- Q が空になるまで、以下の処理を繰り返します。
- u = Q の中で d[u] の値が最小である頂点を選択します。
- Q から u を取り除きます。これで、頂点 u までの最短距離 d[u] が確定しました。
- リラクゼーション: 頂点 u から出る辺 (u, v) が存在する、すべての隣接頂点 v について、以下の処理を行います。
  - もし v がまだ Q に含まれている（つまり、まだ最短距離が確定していない）ならば：
  - 新しい経路の距離 new_dist = d[u] + w(u, v) を計算します。
  - もし new_dist < d[v] ならば（より短い経路が見つかった！）：
    - d[v] = new_dist （vの暫定距離を更新）
    - π[v] = u （vの直前の頂点をuに更新）
終了:
- Q が空になったとき、すべての頂点vについてd[v]にはsからvへの最短距離が格納されています。π配列/マップを使って、逆向きにたどることで最短経路を復元できます。

経路復元:
始点sから任意の頂点tへの最短経路を知りたい場合、π配列をtから逆向きにたどります。
経路 = [t]
current = t
while current != s:
current = π[current]
経路.insert(0, current) # 経路の先頭に追加
経路が [s, …, t] の順で得られます。

リラクゼーション操作の詳細

リラクゼーション操作 if d[u] + w(u, v) < d[v] と d[v] = d[u] + w(u, v); π[v] = u; は、ダイクストラ法だけでなく、多くの最短経路アルゴリズム（ベルマン・フォード法、SPFAなど）で共通して行われる操作です。

この操作は、ある頂点 v への既知の暫定的な最短距離 d[v] を、別の頂点 u を経由して v に到達する新しい経路の距離 d[u] + w(u, v) と比較し、もし新しい経路の方が短ければ d[v] を更新するというものです。

この操作を繰り返すことで、各頂点 v の d[v] の値は、最初は無限大から始まり、発見されるより短い経路によって徐々に小さくなっていきます。最終的に、適切なアルゴリズム（ここではダイクストラ法）によってすべてのリラクゼーションが行き尽くされると、d[v] は s から v への真の最短距離に収束します。

ダイクストラ法では、このリラクゼーションを「最短距離が確定した頂点 u」から出る辺に対して行います。この順序付けが、辺の重みが非負である場合に正しさを保証する鍵となります。

アルゴリズムの例

具体的なグラフを使って、ダイクストラ法の動作を見てみましょう。

以下のグラフを考えます。頂点はA, B, C, D, Eの5つで、始点をAとします。辺に付いている数値が重みです。

10 1 A -----> B -----> C | | | 6 | 3 | 9 | | | | v v v D -----> E -----> C 2 4

厳密にはこれは有向グラフとして扱います。
辺: (A, B, 10), (A, D, 6), (B, D, 3), (B, E, 1), (D, E, 2), (E, C, 4), (C, B, 1) （逆向きの辺も含まれる場合、無向グラフとして扱う）
例では、Aを始点とするので、Aから到達可能な頂点への最短経路を求めます。

データ構造の初期化:
* d: {A: 0, B: ∞, C: ∞, D: ∞, E: ∞}
* π: {A: NIL, B: NIL, C: NIL, D: NIL, E: NIL}
* Q: {A, B, C, D, E}

メインループ開始:

ステップ 1:
1. Q の中で d の値が最小の頂点を選択します。d[A]=0 が最小です。u = A を選択します。
2. Q から A を取り除きます。Q = {B, C, D, E}。d[A] (0) が確定しました。
3. A から出る辺についてリラクゼーションを行います。
* 辺 (A, B), 重み 10: v = B。new_dist = d[A] + w(A, B) = 0 + 10 = 10。d[B] (∞) より小さいので更新。
* d[B] = 10
* π[B] = A
* 辺 (A, D), 重み 6: v = D。new_dist = d[A] + w(A, D) = 0 + 6 = 6。d[D] (∞) より小さいので更新。
* d[D] = 6
* π[D] = A
d: {A: 0, B: 10, C: ∞, D: 6, E: ∞}
π: {A: NIL, B: A, C: NIL, D: A, E: NIL}

ステップ 2:
1. Q = {B, C, D, E} の中で d の値が最小の頂点を選択します。d[D]=6 が最小です。u = D を選択します。
2. Q から D を取り除きます。Q = {B, C, E}。d[D] (6) が確定しました。
3. D から出る辺についてリラクゼーションを行います。
* 辺 (D, E), 重み 2: v = E。new_dist = d[D] + w(D, E) = 6 + 2 = 8。d[E] (∞) より小さいので更新。
* d[E] = 8
* π[E] = D
d: {A: 0, B: 10, C: ∞, D: 6, E: 8}
π: {A: NIL, B: A, C: NIL, D: A, E: D}

ステップ 3:
1. Q = {B, C, E} の中で d の値が最小の頂点を選択します。d[E]=8 が最小です。u = E を選択します。
2. Q から E を取り除きます。Q = {B, C}。d[E] (8) が確定しました。
3. E から出る辺についてリラクゼーションを行います。
* 辺 (E, C), 重み 4: v = C。new_dist = d[E] + w(E, C) = 8 + 4 = 12。d[C] (∞) より小さいので更新。
* d[C] = 12
* π[C] = E
d: {A: 0, B: 10, C: 12, D: 6, E: 8}
π: {A: NIL, B: A, C: E, D: A, E: D}

ステップ 4:
1. Q = {B, C} の中で d の値が最小の頂点を選択します。d[B]=10 が最小です。u = B を選択します。
2. Q から B を取り除きます。Q = {C}。d[B] (10) が確定しました。
3. B から出る辺についてリラクゼーションを行います。
* 辺 (B, D), 重み 3: v = D。D はすでに Q から取り除かれています（最短距離確定済み）。リラクゼーションは行いません。
* 辺 (B, E), 重み 1: v = E。E はすでに Q から取り除かれています（最短距離確定済み）。リラクゼーションは行いません。
d: {A: 0, B: 10, C: 12, D: 6, E: 8}
π: {A: NIL, B: A, C: E, D: A, E: D}

ステップ 5:
1. Q = {C} の中で d の値が最小の頂点を選択します。d[C]=12 が最小です。u = C を選択します。
2. Q から C を取り除きます。Q = {}。d[C] (12) が確定しました。
3. C から出る辺についてリラクゼーションを行います。
* 辺 (C, B), 重み 1: v = B。B はすでに Q から取り除かれています（最短距離確定済み）。リラクゼーションは行いません。
d: {A: 0, B: 10, C: 12, D: 6, E: 8}
π: {A: NIL, B: A, C: E, D: A, E: D}

メインループ終了: Q が空になりました。

結果:
始点Aからの各頂点への最短距離は以下の通りです。
* A -> A: 0
* A -> B: 10
* A -> C: 12
* A -> D: 6
* A -> E: 8

最短経路の復元:
* A -> C: π[C]=E, π[E]=D, π[D]=A. 逆向きにたどると A <- D <- E <- C。経路は A -> D -> E -> C。重み合計は 6 + 2 + 4 = 12。これは d[C] と一致します。
* A -> B: π[B]=A. 逆向きにたどると A <- B。経路は A -> B。重み合計は 10。これは d[B] と一致します。
* A -> E: π[E]=D, π[D]=A. 逆向きにたどると A <- D <- E。経路は A -> D -> E。重み合計は 6 + 2 = 8。これは d[E] と一致します。

この例では、AからBへの直接の辺の重みが10でしたが、A -> D -> E -> C -> B の経路も存在します。その重みは 6 + 2 + 4 + 1 = 13 です。ダイクストラ法によって見つかったA -> Bの最短経路はA->B (重み10) であり、これはA->D->E->C->Bよりも短いことが確認できます。

データ構造と計算量

ダイクストラ法の効率は、未確定頂点の集合 Q の中で距離が最小の頂点を選択し、取り出す操作をどれだけ効率的に行えるかにかかっています。

素朴な実装 (配列/リストと線形探索)

Q を単純な配列やリストで管理し、最小距離の頂点を毎回線形探索する場合を考えます。

初期化: O(V)
メインループ: V回繰り返されます（各頂点が一度だけQから取り出されるため）。
最小距離の頂点の選択: Q に残っている頂点の数だけ探索が必要です。最悪の場合、Q には O(V) 個の頂点が含まれるため、O(V) かかります。
Q からの取り除き: O(V) （リストの場合）
リラクゼーション: 各辺 (u, v) について一度だけ行われます。合計で E 回のリラクゼーションが発生します。各リラクゼーションでは、v が Q に含まれているかどうかの判定が必要になる場合があります（これも線形探索なら O(V)）。
- しかし、通常の実装では、Q には頂点そのものが入っており、その頂点の「状態」（確定済みか未確定か）を別途管理するフラグ配列などで判定することが多いです。その場合、リラクゼーション自体の計算量は辺の重み参照や配列更新などで O(1) ですが、隣接頂点vがQに含まれているかの判定は、QがリストであればO(V)かかります。

この素朴な実装では、メインループが一回回るごとに「最小選択 (O(V)) + 取り除き (O(V)) + リラクゼーション (最大で O(E * V) かかる可能性があるが、実際は各頂点からの辺についてのみ行うので合計で O(E) 回のリラクゼーション呼び出し自体は発生。ただしvがQに含まれているかの判定がO(V)なら全体でO(VE))」となります。しかし、最も支配的なのは「最小選択」の V回の合計であり、各回 O(V) なので、全体の計算量は O(V^2) となります。

計算量: O(V^2)

この計算量は、グラフが密な場合（辺の数 E が頂点数の2乗 V^2 に近い場合）には悪くありませんが、疎な場合（E << V^2）には効率が悪くなります。

優先度付きキューを使った実装

ダイクストラ法の効率を大幅に向上させるには、未確定頂点の集合 Q の中で距離が最小の頂点を素早く見つけることができるデータ構造が必要です。そこで使われるのが「優先度付きキュー (Priority Queue)」です。

優先度付きキューは、要素に優先度（この場合は暫定距離 d[v]）が割り当てられており、以下の操作を効率的に行えます。
* 要素の挿入 (Insert): O(log N) （Nはキュー内の要素数）
* 最小優先度の要素の取り出し (Extract-Min): O(log N)
* 既存要素の優先度更新 (Decrease-Key/Update): O(log N) （多くのヒープベースの優先度付きキューでサポートされている）

ダイクストラ法で優先度付きキューを使う場合、Q は頂点と暫定距離のペア (v, d[v]) を要素とする優先度付きキューになります。優先度は距離 d[v] です。

アルゴリズム手順 (優先度付きキュー版):

初期化:
- すべての頂点 v ∈ V に対して d[v] = ∞, π[v] = NIL。
- d[s] = 0。
- Q を空の優先度付きキューとして初期化します。
- すべての頂点 v ∈ V を、優先度 d[v] として Q に挿入します。注意: 最初は d[s]=0、他は∞なので、s が最初に最小要素として取り出されることになります。あるいは、sだけを優先度0で挿入し、他の頂点は必要になったら挿入・更新するという方法もありますが、ここでは最初からすべてを挿入する方法で考えます。
メインループ:
- Q が空になるまで繰り返します。
- u = Q から最小優先度（最小距離）の要素（頂点）を取り出します (Extract-Min)。
- 重要な注意: 優先度付きキューの中には、同じ頂点に対して複数のエントリが存在する可能性があります（リラクゼーションで距離が更新されるたびに新しいエントリを追加し、古いものを放置する場合）。この場合、Q から取り出された頂点 u が、既に最短距離が確定した頂点であるか（つまり、以前により小さい距離で一度取り出されたことがあるか）を確認する必要があります。もしそうなら、その u は古いエントリなので無視します。効率的な実装では、このチェックを省略し、Q から取り出された頂点が初めて取り出された際にその距離を確定した距離とみなします。ここで取り出された距離 d[u] がsからuへの最短距離になります。
- u から出る辺 (u, v) が存在する、すべての隣接頂点 v についてリラクゼーションを行います。
  - 新しい経路の距離 new_dist = d[u] + w(u, v) を計算します。
  - もし new_dist < d[v] ならば：
    - d[v] = new_dist
    - π[v] = u
    - v を新しい優先度 d[v] で Q に挿入または更新します。もし v がすでに Q に存在する場合は、その優先度を new_dist に更新します (Decrease-Key)。多くの標準ライブラリの優先度付きキューは Decrease-Key を直接サポートしていない場合があるため、その場合は新しいエントリ (v, new_dist) を追加し、古いエントリは取り出された際に無視するというテクニックを使います。

計算量 (優先度付きキュー版):

初期化: すべての頂点を優先度付きキューに挿入するのに O(V log V)。
メインループ:
- 各頂点は高々一度だけ優先度付きキューから取り出されます (Extract-Min)。V回の Extract-Min 操作が発生し、合計 O(V log V)。
- 各辺 (u, v) について高々一度だけリラクゼーション操作が行われます。合計 E 回のリラクゼーションが発生します。
- リラクゼーションで d[v] が更新されるたびに、優先度付きキュー内の頂点 v の優先度を更新 (Decrease-Key) するか、新しいエントリを挿入します。Decrease-Key は O(log V)、挿入も O(log V) です。
- 合計で E 回のリラクゼーションがあり、各リラクゼーションが優先度付きキューの操作を伴うため、リラクゼーション全体の計算量は O(E log V)。

したがって、優先度付きキューを使ったダイクストラ法の全体の計算量は、初期化とメインループの計算量を合わせて O(V log V + E log V) = O((V + E) log V) となります。

多くの場合、グラフの辺の数 E は頂点数 V よりも多い、あるいは同程度なので、O(V^2) より O((V+E) log V) の方が効率的です。特に疎なグラフ (E が V^2 に比べて非常に小さい) では、この差は顕著になります。

例えば、V=1000, E=10000 の場合、O(V^2) は 1,000,000、O((V+E) log V) は約 (1000+10000) * log2(1000) ≈ 11000 * 10 = 110000 となり、優先度付きキュー版がはるかに高速です。

ダイクストラ法の正当性

なぜダイクストラ法は正しく最短経路を見つけられるのでしょうか？その正しさは、「貪欲法 (Greedy Algorithm)」の性質と、辺の重みが非負であるという条件に基づいています。

アルゴリズムの各ステップで、未確定集合 Q から暫定距離が最小の頂点 u を選び出し、その距離 d[u] を確定させます。この選択が「貪欲」な選択です。なぜこの貪欲な選択が最適解（最短距離）につながるのでしょうか？

重要なのは、頂点 u が Q の中で暫定距離が最小であるということです。つまり、d[u] <= d[v] for all v ∈ Q です。

ここで、d[u] が実はsからuへの真の最短距離ではないと仮定してみましょう。もしそうであれば、sからuへの真の最短経路 P が存在するはずです。この経路 P は、u以外にもまだ Q に含まれる頂点を含んでいるかもしれません。経路 P 上で、sから出発して初めて Q に含まれる頂点に出会う点を y、そしてその直前の点を x とします。このとき、x は必ずQ からすでに削除された、つまり最短距離が確定した頂点です（そうでなければ、y がP上で初めてQに出会う頂点であるという定義に反します）。

経路 P におけるsからxまでの部分はsからxへの最短経路です（そうでなければP全体を短縮できてしまう）。そして、ダイクストラ法はxまでの最短距離d[x]を正しく確定させています。したがって、sからyまでの経路のうち、xを経由する経路の距離は d[x] + w(x, y) です。

ダイクストラ法は、xが確定した際に辺(x, y)についてリラクゼーションを行っているはずです。その結果、yの暫定距離 d[y] は高々 d[x] + w(x, y) に更新されているはずです。つまり、d[y] <= d[x] + w(x, y) です。

さて、P上のsからyまでの距離は d[x] + w(x, y) です。そして、P上のyからuまでの残りの経路の距離は、辺の重みがすべて非負であるため、0以上です。したがって、Pの全体の距離は d[x] + w(x, y) + (Pのyからuまでの距離) >= d[x] + w(x, y) です。

つまり、sからuへの真の最短経路Pの距離は d[x] + w(x, y) 以上ということになります。そして、私たちは d[y] <= d[x] + w(x, y) という関係を知っています。

さらに、y はまだ Q に含まれる頂点であり、u は Q の中で最小距離の頂点として選ばれました。これは d[u] <= d[y] を意味します。

これらをまとめると、
d[u] <= d[y] <= d[x] + w(x, y) <= (sからuへの真の最短経路Pの距離)
となります。

もし d[u] がsからuへの真の最短距離よりも小さいと仮定したとすれば、これは矛盾です。
また、もし d[u] がsからuへの真の最短距離よりも大きいと仮定したとすれば、sからuへの真の最短経路 P 上には必ず Q に含まれる頂点 y が存在し、d[y] はP上のsからyまでの距離に更新されているはずです。そして、P上のsからyまでの距離は、sからuまでの真の最短距離よりも小さいはずです。これは d[u] が Q の中で最小として選ばれたという仮定に反する可能性があります（d[y] < d[u] となる y が Q に残っていることになってしまう）。

この説明はやや直感的ですが、より厳密な帰納法を用いた証明では、ダイクストラ法によって Q から取り出された頂点 u に対して d[u] が常にsからuへの真の最短距離に等しいことが証明できます。この証明において、辺の重みが非負であることは不可欠です。負の重みがある場合、d[x] + w(x, y) がsからyへの真の最短距離よりも小さく、かつyからuへの経路の合計重みが負になることで、sからuへの真の最短経路の距離が d[y] よりも小さくなる可能性が生じます。つまり、u を選択して確定させた時点では u の暫定距離が最小であっても、後から Q に含まれる他の頂点 v が確定したことで、v を経由する u へのより短い経路が見つかる可能性があるのです。ダイクストラ法はこの可能性を考慮していません。

ダイクストラ法の応用例

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

ナビゲーションシステム: カーナビや公共交通機関の乗り換え案内は、典型的な最短経路問題です。道路や路線を辺、交差点や駅を頂点、辺の重みを距離や所要時間とすることで、最短距離や最短時間の経路を計算します。通行止めや渋滞情報（重みの増加）なども考慮して動的に経路を計算することも可能です。
ネットワークルーティング: インターネットなどの通信ネットワークにおいて、データパケットを送信元から宛先まで最も効率的に（最短時間、最小コストなど）転送する経路を見つけるのにダイクストラ法やその派生アルゴリズムが使われます。ルーターが頂点、通信回線が辺、遅延や帯域幅などが重みとなります。
物流・配送計画: 配送センターから複数の配送先への最適な配送ルートを計画する際に、最短経路や巡回セールスマン問題（こちらはより複雑）の一部としてダイクストラ法が利用されます。倉庫や店舗が頂点、移動コストや時間が辺の重みです。
ゲームAI: ゲームキャラクターが目標地点まで移動する際に、障害物を避けつつ最短経路を見つけるためにダイクストラ法やA*アルゴリズム（ダイクストラ法を拡張し、目的地までの推定距離を考慮することで探索を効率化する）が使われます。ゲームマップの各タイルや交差点が頂点、移動コストが辺の重みになります。
回路設計: 集積回路の設計において、信号が最も速く伝わる経路（最小遅延経路）を見つけるために使用されることがあります。
生物学: DNAやタンパク質の配列アライメント（類似性の高い並び方を見つける）において、編集距離（ある配列を別の配列に変換するのに必要な最小の操作回数）を計算するのに最短経路問題として定式化できる場合があります。
金融: 為替市場における裁定取引（アービトラージ）の機会を見つける問題が、対数を取ると最短経路問題として定式化できる場合があります。各通貨を頂点、為替レートの対数の負の値を辺の重みとすることで、負のサイクル（無限に利益を上げられる経路）の検出にベルマン・フォード法などが使われますが、辺の重みが非負に変換可能であればダイクストラ法も応用可能です。

これらの応用例からもわかるように、ダイクストラ法は様々な分野で「最適な経路」を見つけるための基本的なツールとして活用されています。

注意点と制限

ダイクストラ法は非常に強力なアルゴリズムですが、万能ではありません。いくつか重要な注意点と制限があります。

負の重み: 最も重要な制限は、辺の重みが非負である必要があるという点です。前述のように、負の重みがあると、アルゴストラが「確定」させた距離が真の最短距離にならない可能性があります。負の重みが存在するグラフの最短経路問題には、ベルマン・フォード法やSPFA (Shortest Path Faster Algorithm) といった他のアルゴリズムを使用する必要があります。これらのアルゴリズムは負の重みを扱えますが、一般にダイクストラ法より計算量が大きくなります。また、負の閉路（辺の重みの合計が負になるサイクルのこと）が存在する場合、最短経路は定義できなくなる（サイクルを無限に周回することで距離をいくらでも小さくできてしまう）ため、ベルマン・フォード法などは負の閉路を検出する機能も持っています。
単一始点: ダイクストラ法は、一つの始点から他のすべての頂点への最短経路を計算します。もし、グラフ内のすべての頂点ペア間の最短経路を知りたい場合は、各頂点を始点としてV回ダイクストラ法を実行するか（全ペア最短経路問題、計算量 O(V(V+E) log V)）、あるいはFloyd-Warshallアルゴリズム（計算量 O(V^3)）やJohnsonのアルゴリズム（計算量 O(V log V + VE)）といった別のアルゴリズムを使用するのが効率的です。
計算量の選択: ダイクストラ法の計算量は、使用するデータ構造に依存して O(V^2) または O((V+E) log V) となります。グラフの性質（密か疎か）や V, E の規模に応じて、より効率的な実装を選択することが重要です。現実世界の大規模なグラフは疎であることが多いので、優先度付きキューを使った O((V+E) log V) 版がよく用いられます。
空間計算量: 隣接リスト表現を使う場合、空間計算量は O(V + E) です。距離や直前頂点を記録する配列は O(V) です。優先度付きキューも最悪の場合 O(V) の要素を格納します。全体として O(V + E) の空間が必要になります。

これらの制限を理解した上で、問題に適したアルゴリズムを選択することが重要です。

実装例 (Python)

優先度付きキュー（Pythonのheapqモジュール）を使ったダイクストラ法の簡単な実装例を示します。グラフは隣接リストで表現します。

“`python
import heapq
import math # 無限大を表すためにmath.infを使用

グラフを隣接リストで表現

graph = { 頂点: [(隣接頂点, 重み), …] }

graph = {
‘A’: [(‘B’, 10), (‘D’, 6)],
‘B’: [(‘D’, 3), (‘E’, 1)],
‘C’: [(‘B’, 1)],
‘D’: [(‘E’, 2)],
‘E’: [(‘C’, 4)],
‘F’: [] # 孤立した頂点も考慮
}

def dijkstra(graph, start_node):
“””
ダイクストラ法により、指定された始点から他のすべての頂点への最短経路距離を計算する。

Args:
    graph (dict): グラフを表す隣接リスト {node: [(neighbor, weight), ...]}
    start_node (str): 始点のノード名

Returns:
    tuple: (distances, predecessors)
           distances (dict): 始点から各頂点への最短距離 {node: distance}
           predecessors (dict): 最短経路で各頂点の直前の頂点 {node: predecessor_node}
"""

# 1. 初期化
distances = {node: math.inf for node in graph}
predecessors = {node: None for node in graph}
distances[start_node] = 0

# 優先度付きキュー (距離, 頂点) のタプルを格納
# heapqは最小ヒープなので、距離が小さいものから取り出される
priority_queue = [(0, start_node)]

# 距離が確定した頂点のセット (これは効率のために使うこともあるが、ここではpriority_queueとdの値で管理)
# visited = set()

# 2. メインループ
while priority_queue:
    # Qから最小距離の頂点uを取り出す (Extract-Min)
    current_distance, u = heapq.heappop(priority_queue)

    # # 既に最短距離が確定済みの場合はスキップ (古いエントリを無視するテクニック)
    # if u in visited:
    #     continue
    # visited.add(u)

    # 取り出した距離が現在の最短距離より大きい場合は、それは古い（より長い）経路なので無視
    # priority_queueに重複したエントリが存在する場合に有効
    if current_distance > distances[u]:
        continue

    # uから出る辺についてリラクゼーション
    if u in graph: # グラフに存在しない頂点（入力ミスなど）の対応
        for v, weight in graph[u]:
            # vがgraphのキーとして存在するかチェック (グラフの整合性)
            if v in graph:
                new_distance = distances[u] + weight

                # より短い経路が見つかった場合
                if new_distance < distances[v]:
                    distances[v] = new_distance
                    predecessors[v] = u
                    # 優先度付きキューにvとその新しい距離を追加
                    heapq.heappush(priority_queue, (new_distance, v))
            else:
                 print(f"Warning: Edge from {u} to unknown vertex {v}")


# 結果を返す
return distances, predecessors

始点を指定してダイクストラ法を実行

start = ‘A’
distances, predecessors = dijkstra(graph, start)

結果表示

print(f”始点 {start} から各頂点への最短距離:”)
for node, dist in distances.items():
if dist == math.inf:
print(f” {node}: 到達不可能”)
else:
print(f” {node}: {dist}”)

print(“\n最短経路 (predecessors):”)
for node, pred in predecessors.items():
print(f” {node}: {pred}”)

例: 特定の頂点への最短経路を復元

def reconstruct_path(predecessors, start_node, end_node):
“””
predecessors情報を使って、始点から終点への最短経路を復元する。
“””
path = []
current = end_node
while current is not None:
path.insert(0, current)
if current == start_node:
break
current = predecessors[current]

# 経路が存在しない場合 (終点がstart_nodeに到達不可能)
if path[0] != start_node:
    return [] # またはNone

return path

end = ‘C’
path_to_c = reconstruct_path(predecessors, start, end)
if path_to_c:
print(f”\n{start} から {end} への最短経路:”)
print(” -> “.join(path_to_c))
else:
print(f”\n{start} から {end} へは到達できません。”)

end_f = ‘F’
path_to_f = reconstruct_path(predecessors, start, end_f)
if path_to_f:
print(f”\n{start} から {end_f} への最短経路:”)
print(” -> “.join(path_to_f))
else:
print(f”\n{start} から {end_f} へは到達できません。”)

“`

コードの解説:

インポート: heapq モジュール（優先度付きキューの実装）と math モジュール（無限大 math.inf のために）をインポートします。
グラフ表現: Pythonの辞書を使ってグラフを表現しています。キーが頂点名、値がその頂点から出る辺のリストです。各辺は (隣接頂点, 重み) のタプルで表されます。
初期化: distances 辞書は各頂点への暫定距離を保持し、最初は始点以外は math.inf に設定されます。predecessors 辞書は最短経路上の直前の頂点を記録し、経路復元に使用します。始点の距離は0に設定されます。
優先度付きキュー: priority_queue は (距離, 頂点名) のタプルを要素とするリストとして初期化され、heapq モジュールの関数を使ってヒープとして扱われます。最初に (0, start_node) を挿入します。
メインループ: priority_queue が空になるまで続きます。
最小要素の取り出し: heapq.heappop(priority_queue) は、キューの中で最小の距離を持つ要素（タプル）を取り出します。取り出された頂点 u の距離 current_distance が、現在の distances[u] よりも大きい場合は、それは古い（より長い経路で見つかった）情報なので無視します。これは、heapq が Decrease-Key を直接サポートしないため、距離が更新されるたびに新しいエントリを追加する戦略を取っているため必要になるチェックです。
リラクゼーション: 取り出した頂点 u から出るすべての辺 (u, v) について処理します。新しい距離 new_distance = distances[u] + weight を計算し、もし distances[v] よりも小さければ、distances[v] と predecessors[v] を更新します。そして、更新された (new_distance, v) を優先度付きキューに heapq.heappush で追加します。
終了: priority_queue が空になったとき、到達可能なすべての頂点への最短距離が distances に、経路情報が predecessors に格納されています。
経路復元関数: reconstruct_path 関数は、predecessors 情報を使って終点から始点へ逆向きにたどることで、最短経路のリストを構築します。

この実装は、優先度付きキューを使用しているため、計算量は O((V + E) log V) となり、効率的です。

まとめ

この記事では、グラフの最短経路問題を解くための最も基本的で広く使われているアルゴリズム、ダイクストラ法について詳細に解説しました。

ダイクストラ法は、単一の始点からグラフ内の他のすべての頂点への最短経路を、辺の重みが非負である場合に限って計算します。その基本的なアイデアは、始点から近い順に頂点までの最短距離を「確定」させていく、というものです。

アルゴリズムは以下のステップで進行します。
1. 始点距離を0、他を無限大に初期化し、すべての頂点を未確定集合（優先度付きキュー）に入れる。
2. 未確定集合の中で暫定距離が最小の頂点を選び、確定させる。
3. 確定した頂点から出る辺を使って、隣接する未確定頂点の暫定距離を更新する（リラクゼーション）。
4. すべての頂点が確定するか、未確定集合が空になるまで繰り返す。

このプロセスにおいて、優先度付きキューを使用することで、計算量を効率的に O((V+E) log V) に抑えることができます。

ダイクストラ法は、ナビゲーション、ネットワークルーティング、物流など、様々な分野で「最適化」のための基盤技術として応用されています。

ただし、ダイクストラ法には「辺の重みが非負であること」という重要な制限があります。負の重みを持つグラフには適用できず、その場合はベルマン・フォード法などの別のアルゴリズムが必要です。

この記事を通して、ダイクストラ法の仕組み、アルゴリズムの具体的な流れ、計算量の分析、そしてPythonでの簡単な実装例を理解いただけたことと思います。最短経路問題はグラフ理論の入り口であり、ダイクストラ法はその扉を開く鍵の一つです。

これを機に、さらに他のグラフアルゴリズム（BFS, DFS, Kruskal, Prim, Bellman-Ford, Floyd-Warshallなど）や、最短経路問題の応用（A*アルゴリズム、巡回セールスマン問題など）について深く学んでみるのも良いでしょう。グラフ理論の世界は非常に広く深く、探求する価値のある分野です。

グラフとアルゴリズムの力を活用して、様々な問題の最適な解を見つけ出してください！