プログラミングに役立つ！Dijkstra 算法（ダイクストラ法）入門

By /

プログラミングに役立つ！Dijkstra 算法（ダイクストラ法）入門

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

プログラミングを学んでいる皆さん、あるいはこれから学ぼうとしている皆さん。アルゴリズムという言葉を聞いたことがあるでしょうか？アルゴリズムとは、特定の課題を解決するための一連の手順や計算方法のことです。プログラミングは、まさにこのアルゴリズムをコンピュータが理解できる形で記述することに他なりません。

数あるアルゴリズムの中でも、非常に実用的で応用範囲が広く、かつ理解することでグラフ理論の基礎や効率的なデータ構造の使い方を学ぶことができるものの一つに、「Dijkstra 算法（ダイクストラ法）」があります。ダイクストラ法は、グラフ理論における「最短経路問題」を解くための代表的なアルゴリズムです。

「最短経路問題」と聞くと、皆さんが日常的に使っているスマートフォンの地図アプリを思い浮かべるかもしれません。「自宅から目的地まで、渋滞を避けて最短時間で移動したい」──これはまさに最短経路問題の一つです。あるいは、インターネット上でデータがパケットとして送信されるとき、どの経路を通れば最も速く、あるいは最も効率的に目的地に到達できるか──これもまた最短経路問題です。

ダイクストラ法は、このような最短経路問題を、特に「辺（つながり）に非負の重み（コストや距離など）が付いているグラフ」において、出発点から他の全ての頂点（場所や地点）への最短経路を見つけ出すのに非常に強力なツールとなります。

この記事では、ダイクストラ法が一体どのようなもので、どのように動作し、なぜプログラミング学習において重要なのかを、初心者の方にも分かりやすく、かつ詳細に解説していきます。理論的な背景から、アルゴリズムの詳細なステップ、具体的な例を使った解説、そしてPythonを使った実装例まで、約5000語にわたってたっぷりとご紹介します。

この記事を最後まで読んでいただければ、あなたはダイクストラ法の基本原理をしっかりと理解し、自分の手でコードを書いて shortest path を計算できるようになるでしょう。さあ、ダイクストラ法の世界へ一緒に踏み出しましょう！

グラフとは何か？最短経路問題の舞台設定

ダイクストラ法を理解するためには、まずその対象となる「グラフ」と、「最短経路問題」がどのようなものかをしっかりと把握しておく必要があります。

グラフの基本概念

ここでいう「グラフ」とは、数学や情報科学の分野で使われる特別な構造を持つグラフのことです。日常的に使う棒グラフや折れ線グラフとは異なります。数学的なグラフは、以下の二つの要素で構成されます。

  1. 頂点 (Vertex / Node): 物事や地点を表します。例えば、地図上の都市、コンピュータネットワークのルーター、人間の関係ネットワークにおける個人などが頂点にあたります。頂点はしばしば記号（A, B, C, …）や番号（0, 1, 2, …）で表されます。
  2. 辺 (Edge): 頂点と頂点の間の関係やつながりを表します。例えば、都市間の道路、ルーター間のケーブル、人々の間の友情などが辺にあたります。辺は二つの頂点を結びつけます。

グラフにはいくつかの種類があります。

  • 無向グラフ (Undirected Graph): 辺につながりの方向性がないグラフです。例えば、「AからBへの道」と「BからAへの道」が同じであるような場合です。辺は単に {A, B} のように二つの頂点の集合として表されます。
  • 有向グラフ (Directed Graph): 辺につながりの方向性があるグラフです。例えば、「一方通行の道」や「ウェブサイト上のリンク」のような場合です。辺は順序付けられたペア (A, B) のように表され、AからBへは行けますが、BからAへは直接行けない可能性があります。

ダイクストラ法は、通常、有向グラフまたは無向グラフ（無向グラフは、双方向の辺を持つ有向グラフとみなすことができます）に対して適用されます。

重み付きグラフ (Weighted Graph)

さらに、最短経路問題を考える上で重要なのが「重み付きグラフ」です。これは、それぞれの辺に数値、すなわち「重み (Weight)」が関連付けられたグラフです。この重みは、辺を通る際のコスト、距離、時間、あるいはその他の尺度を表します。

  • 地図アプリなら、辺の重みは道路の「距離」や通行にかかる「時間」かもしれません。
  • ネットワークなら、辺の重みはデータの転送にかかる「時間」や「コスト」かもしれません。
  • 物流ネットワークなら、辺の重みは商品の運搬にかかる「コスト」や「時間」かもしれません。

最短経路問題は、この重み付きグラフの上で定義されます。

最短経路問題の定義

最短経路問題とは、重み付きグラフにおいて、特定の開始頂点から、他の全ての頂点（または特定の目的頂点）までの経路の中で、辺の重みの合計が最小となる経路を見つける問題です。

例えば、出発点Aから、頂点X、Y、Zそれぞれへの最短経路を見つけたいとします。考えられる経路は複数あるでしょう。それぞれの経路は、経由する辺の重みを合計することで、その経路全体の「コスト」や「長さ」を計算できます。最短経路問題は、その合計が最も小さくなる経路を探し出すことを目指します。

ダイクストラ法は、この問題の「単一始点最短経路問題（Single-Source Shortest Path Problem）」と呼ばれるバリエーションを解くためのアルゴリズムです。つまり、一つの決まった出発点から、グラフ内の他の全ての頂点への最短経路を効率的に見つけ出します。

ただし、ダイクストラ法には重要な制約があります。それは、辺の重みが全て非負（ゼロ以上）である必要があるという点です。もしグラフに負の重みを持つ辺が存在する場合、ダイクストラ法は正しく動作しません。負の重み辺がある場合の最短経路問題には、ベルマン・フォード法などの別のアルゴリズムを使用する必要があります。

ダイクストラ法、その考え方と目的

ダイクストラ法は、オランダの計算機科学者エドガー・ダイクストラによって1956年に考案され、1959年に発表されたアルゴリズムです。その基本的な考え方は非常に直感的でありながら、巧妙です。

基本的な考え方：近いところから確定していく

ダイクストラ法の根底にあるアイデアは、「出発点から最も近い（距離が最小の）頂点から順番に、その頂点までの最短距離を確定させていく」というものです。

アルゴリズムは、出発点から開始します。出発点から直接到達できる頂点の中で、最も近い頂点を特定します。その頂点までの距離は、出発点からその頂点への辺の重みそのものです。この距離は、他のどの経路を通るよりも短いことが保証されます（なぜなら、他の経路は少なくとももう一本辺を通る必要があり、辺の重みは非負だからです）。

次に、その「最短距離が確定した頂点」を経由することで、他の未確定の頂点への距離が短くなる可能性があるかを調べます。もし、その確定した頂点を経由することで、ある頂点へのこれまでの最短候補距離よりも短い経路が見つかった場合、その距離を更新します。

このプロセスを、まだ最短距離が確定していない頂点の中で、出発点から最も近い頂点を繰り返し選び出し、その頂点から延びる辺を使って他の頂点への距離を更新していく形で続けます。全ての頂点への最短距離が確定するか、目的の頂点への最短距離が確定するまで繰り返します。

例えるなら、水が出発点から低い方へ流れていくイメージや、伝染病が最初に発生した地点から感染しやすい人に広がっていくイメージに近いかもしれません。出発点から「距離」という「高さ」が低い方へ、つまり最短の経路を辿って情報が伝播し、到達した地点の最短距離を更新していくのです。

なぜ非負の重みが必要なのか？

ダイクストラ法が非負の重みを持つ辺にのみ適用できる理由は、この「近いところから確定していく」という性質にあります。

ある頂点Uまでの最短距離が確定したとします。これは、出発点からUまでの経路の中で、Uまでのコストが最小であるということです。もし辺の重みが全て非負であれば、Uを経由して他の頂点Vへ行く場合、その経路の合計コストは「出発点からUまでの最短距離 + UからVへの辺の重み」となります。辺の重みが非負なので、この合計コストは必ず「出発点からUまでの最短距離」以上になります。つまり、既に最短距離が確定している頂点よりも、さらに距離が短くなることはありえません。

しかし、もしUからVへの辺の重みが負だった場合、「出発点からUまでの最短距離 + 負の重み」は、「出発点からUまでの最短距離」よりも小さくなってしまいます。これは、「近いところから確定」したはずのUよりも、Uを経由したVの方が実際には出発点から見て近くなる可能性があることを意味します。このため、「一度確定した最短距離が後から覆される可能性がある」ことになり、ダイクストラ法の「近いところから順に確定する」という前提が崩れてしまいます。

したがって、ダイクストラ法は負の重みを持つ辺があるグラフには適用できません。

他のアルゴリズムとの比較（簡易版）

  • ベルマン・フォード法: 負の重みを持つ辺があるグラフでも最短経路問題を解くことができます。ただし、負の閉路（経路上の辺の重みの合計が負になるような循環）が存在すると、最短経路が定義できなくなる場合があります（いくらでもコストを小さくできる）。計算量はダイクストラ法より一般的に大きいです。
  • A*アルゴリズム: ダイクストラ法を拡張したもので、目的の頂点がある場合に、探索の方向を賢く誘導するために「ヒューリスティック関数」を利用します。特に、広い探索空間を持つ問題（ゲームAIの経路探索など）で有効です。基本的な考え方はダイクストラ法に似ていますが、探索効率を向上させます。

ダイクストラ法は、非負重みグラフにおける単一始点最短経路問題に対して、効率的かつ正当な解を与える、非常に重要なアルゴリズムなのです。

ダイクストラ法のアルゴリズム詳細：ステップ・バイ・ステップ解説

いよいよダイクストラ法の具体的なアルゴリズムの手順を詳しく見ていきましょう。どのようなデータ構造を使って、どのような計算を行い、最短経路を求めていくのかを掘り下げます。

必要なデータ構造

ダイクストラ法を実行するために、いくつかの情報を管理する必要があります。

  1. 距離の記録 (Distance Array/Map):

    • 出発点からの各頂点への、現時点での最短候補距離を記録する配列やマップです。
    • 通常 dist[v] のように表し、出発点から頂点 v までの仮の最短距離を保持します。
    • 初期状態では、出発点自身の距離は 0 とし、他の全ての頂点への距離は無限大 (infinity) としておきます。これは「まだ到達方法が分からない、あるいは非常に遠い」ことを意味します。

  2. 訪問済みフラグ (Visited Set/Array):

    • 既に最短距離が確定した頂点を記録するセットや配列です。
    • 通常 visited[v] のように真偽値で表し、頂点 v の最短距離が確定したかどうかを示します。
    • 初期状態では、全ての頂点は未訪問（最短距離未確定）です。

  3. 優先度付きキュー (Priority Queue):

    • これがダイクストラ法を効率的に実行する鍵となるデータ構造です。
    • これは、要素を取り出す際に「優先度」が最も高いもの（ダイクストラ法の場合は距離が最も小さいもの）から取り出せるキューです。
    • 優先度付きキューには、(距離, 頂点) のペアを格納します。常に距離が最小のペアを取り出せるようにします。
    • 初期状態では、出発点 s を (0, s) というペアとしてキューに追加します。

アルゴリズムのステップ

それでは、これらのデータ構造を使って、ダイクストラ法の手順を追ってみましょう。

ステップ 0: 初期化
* グラフの全ての頂点 v に対して、距離 dist[v] を無限大 (infinity) に設定します。
* 出発点 s の距離 dist[s] を 0 に設定します。
* 全ての頂点を未訪問 (visited[v] = False) とします。
* 優先度付きキュー PQ を作成し、出発点を (0, s) というペアで追加します。

ステップ 1: メインループ
* 優先度付きキュー PQ が空になるまで、以下の処理を繰り返します。

ステップ 2: 最小距離の頂点の取り出し
* PQ から、距離が最小であるようなペア (d, u) を取り出します。ここで d は現時点での頂点 u への最短候補距離です。

ステップ 3: 確定済みのチェック
* もし頂点 u が既に訪問済み（visited[u] == True、つまり既に最短距離が確定している）であれば、この頂点は無視し、ループの先頭に戻ります。これは、PQ にはより長い距離で同じ頂点が複数回入る可能性があるためです。最初に短い距離で取り出されたものが、その頂点への最短距離となります。

ステップ 4: 最短距離の確定と訪問済みのマーク
* 頂点 u の最短距離が確定したことになります。visited[u] を True に設定します。これで、この頂点 u への最短距離 dist[u] は最終的な値として確定します。

ステップ 5: 隣接する頂点の緩和処理 (Relaxation)
* 頂点 u から直接辺が出ている全ての隣接頂点 v に対して、以下の「緩和処理」を行います。
* 辺 (u, v) の重みを w とします。
* 「出発点から u までの最短距離 (dist[u]) に、u から v への辺の重み (w) を加えた値 (dist[u] + w)」を計算します。これは、「u を経由して v に到達した場合の距離」です。
* この計算した距離が、現在 v に記録されている最短候補距離 dist[v] よりも小さいかどうかを比較します。
* もし dist[u] + w < dist[v] であれば、より短い経路が見つかったことになります。
* dist[v] を dist[u] + w に更新します。
* 更新された距離 dist[v] と頂点 v をペア (dist[v], v) として、優先度付きキュー PQ に追加します。

ステップ 6: ループの継続
* ステップ 2 に戻り、PQ が空になるまで処理を続けます。

アルゴリズムの終了

優先度付きキューが空になったとき、アルゴリズムは終了します。この時点で、dist 配列（またはマップ）には、出発点 s からグラフ内の到達可能な全ての頂点への最短距離が格納されています。到達不可能な頂点に対しては、距離は無限大のままとなります。

経路の復元

多くの場合、最短距離だけでなく、実際にその最短距離を達成する「経路」自体を知りたいことがあります。経路を復元するためには、アルゴリズム実行中に、各頂点 v に対して、その最短距離が更新される際に「どの頂点 u から到達したか」を記録しておくと便利です。これを「先行頂点 (predecessor)」または「親ノード」として配列 prev[v] に記録しておけば、目的の頂点から出発点まで prev ポインタを辿っていくことで最短経路を逆順に復元できます。

例で理解するダイクストラ法

言葉だけでは分かりにくいので、具体的なグラフを使ってダイクストラ法のステップを追ってみましょう。

以下の簡単なグラフを考えます。頂点は A, B, C, D, E の5つです。辺のラベルは辺の重みを示します。出発点を A とします。

10 1
A -------> B -------> D
| | |
| | |
5 2 4
| | |
v v v
C -------> E <------ D
3 2
これは有向グラフですが、無向グラフの場合も考え方は同じで、双方向に辺を設定すれば良いだけです。ここでは有向グラフとして進めます。

グラフの定義:
* 頂点: {A, B, C, D, E}
* 辺と重み:
* (A, B): 10
* (A, C): 5
* (B, C): 2
* (B, D): 1
* (C, E): 3
* (D, E): 4
* (D, C): 2

出発点: A

データ構造の初期化:

  • dist テーブル: { A: 0, B: inf, C: inf, D: inf, E: inf } (inf は無限大を表す)
  • visited セット: {} (空集合)
  • PQ (優先度付きキュー): [(0, A)] (距離, 頂点) のペア

アルゴリズムの実行:

ステップ 1: PQ には [(0, A)] があります。最小距離は 0。
* PQ から (0, A) を取り出します。
* A はまだ visited ではありません。
* A を visited に追加します。visited = {A}。A への最短距離は dist[A] = 0 で確定。
* A から出る辺を緩和します:
* 辺 (A, B), 重み 10: dist[A] + 10 = 0 + 10 = 10。dist[B] は inf なので、10 < inf は真。dist[B] を 10 に更新。PQ に (10, B) を追加。
* 辺 (A, C), 重み 5: dist[A] + 5 = 0 + 5 = 5。dist[C] は inf なので、5 < inf は真。dist[C] を 5 に更新。PQ に (5, C) を追加。
* 現在の状態:
* dist: { A: 0, B: 10, C: 5, D: inf, E: inf }
* visited: {A}
* PQ: [(5, C), (10, B)] (距離が小さい順に並んでいると仮定)

ステップ 2: PQ には [(5, C), (10, B)] があります。最小距離は 5。
* PQ から (5, C) を取り出します。
* C はまだ visited ではありません。
* C を visited に追加します。visited = {A, C}。C への最短距離は dist[C] = 5 で確定。
* C から出る辺を緩和します:
* 辺 (C, E), 重み 3: dist[C] + 3 = 5 + 3 = 8。dist[E] は inf なので、8 < inf は真。dist[E] を 8 に更新。PQ に (8, E) を追加。
* 現在の状態:
* dist: { A: 0, B: 10, C: 5, D: inf, E: 8 }
* visited: {A, C}
* PQ: [(8, E), (10, B)]

ステップ 3: PQ には [(8, E), (10, B)] があります。最小距離は 8。
* PQ から (8, E) を取り出します。
* E はまだ visited ではありません。
* E を visited に追加します。visited = {A, C, E}。E への最短距離は dist[E] = 8 で確定。
* E から出る辺は（このグラフでは）ありません。緩和処理は行いません。
* 現在の状態:
* dist: { A: 0, B: 10, C: 5, D: inf, E: 8 }
* visited: {A, C, E}
* PQ: [(10, B)]

ステップ 4: PQ には [(10, B)] があります。最小距離は 10。
* PQ から (10, B) を取り出します。
* B はまだ visited ではありません。
* B を visited に追加します。visited = {A, C, E, B}。B への最短距離は dist[B] = 10 で確定。
* B から出る辺を緩和します:
* 辺 (B, C), 重み 2: dist[B] + 2 = 10 + 2 = 12。dist[C] は 5 です。12 < 5 は偽。更新なし。
* 辺 (B, D), 重み 1: dist[B] + 1 = 10 + 1 = 11。dist[D] は inf なので、11 < inf は真。dist[D] を 11 に更新。PQ に (11, D) を追加。
* 現在の状態:
* dist: { A: 0, B: 10, C: 5, D: 11, E: 8 }
* visited: {A, C, E, B}
* PQ: [(11, D)]

ステップ 5: PQ には [(11, D)] があります。最小距離は 11。
* PQ から (11, D) を取り出します。
* D はまだ visited ではありません。
* D を visited に追加します。visited = {A, C, E, B, D}。D への最短距離は dist[D] = 11 で確定。
* D から出る辺を緩和します:
* 辺 (D, E), 重み 4: dist[D] + 4 = 11 + 4 = 15。dist[E] は 8 です。15 < 8 は偽。更新なし。
* 辺 (D, C), 重み 2: dist[D] + 2 = 11 + 2 = 13。dist[C] は 5 です。13 < 5 は偽。更新なし。
* 現在の状態:
* dist: { A: 0, B: 10, C: 5, D: 11, E: 8 }
* visited: {A, C, E, B, D}
* PQ: [] (空になった)

アルゴリズム終了

優先度付きキューが空になったので、アルゴリズムは終了です。最終的な dist テーブルには、出発点 A から各頂点への最短距離が格納されています。

  • A -> A: 0
  • A -> B: 10
  • A -> C: 5
  • A -> D: 11
  • A -> E: 8

確認してみましょう。
* A->B (10)
* A->C (5)
* A->B->D (10+1=11)
* A->C->E (5+3=8)
* A->B->C->E (10+2+3=15) – A->C->E の方が短い
* A->B->D->E (10+1+4=15) – A->C->E の方が短い
* A->C->D (?) – CからDへの直接の辺はない
* A->B->D->C (10+1+2=13) – A->C の方が短い

確かに、計算された距離が最短となっています。

経路の復元（例）

もし経路を復元したい場合、緩和処理の際に距離を更新した時に、どの頂点から来たかを記録しておきます。

  • dist[A] = 0
  • dist[B] が 10 に更新されたとき、来たのは A。prev[B] = A。
  • dist[C] が 5 に更新されたとき、来たのは A。prev[C] = A。
  • dist[D] が 11 に更新されたとき、来たのは B。prev[D] = B。
  • dist[E] が 8 に更新されたとき、来たのは C。prev[E] = C。

これで、例えば E への最短経路を知りたい場合、E から prev を辿ります。
E <- prev[E] C <- prev[C] A。
逆順に並べると A -> C -> E となり、これが最短経路です。

D への最短経路を知りたい場合、D から prev を辿ります。
D <- prev[D] B <- prev[B] A。
逆順に並べると A -> B -> D となり、これが最短経路です。

このように、prev 配列（またはマップ）を使うことで、最短距離だけでなく具体的な経路も取得できます。

ダイクストラ法のプログラミング実装（Python）

それでは、ダイクストラ法を実際にプログラミングしてみましょう。ここでは、コードが比較的読みやすく、データ構造の概念が分かりやすい Python を使用します。

グラフの表現方法として、「隣接リスト」を使います。隣接リストは、各頂点に対して、そこから直接繋がっている頂点とその辺の重みのリストを持つ構造です。辞書（dictionary）やリストを使って表現するのが一般的です。

“`python
import heapq # Pythonの標準ライブラリにある優先度付きキュー

無限大を表す大きな値

INF = float(‘inf’)

def dijkstra(graph, start_node):
“””
ダイクストラ法を使って、指定された開始ノードから他の全てのノードへの
最短距離を計算する関数。

Args:
    graph (dict): グラフを表す隣接リスト。
                  例: { 'A': {'B': 10, 'C': 5}, 'B': {'C': 2, 'D': 1}, ... }
                  外側のキーは出発ノード、内側のキーは隣接ノード、値は辺の重み。
    start_node (str): 処理を開始するノード。

Returns:
    tuple: (distance_map, predecessors_map)
           distance_map (dict): 各ノードへの最短距離。
                                例: {'A': 0, 'B': 10, 'C': 5, ...}
           predecessors_map (dict): 各ノードへの最短経路で、そのノードの直前のノード。
                                   経路復元に使用。例: {'B': 'A', 'C': 'A', ...}
"""
# 全てのノードを取得
nodes = list(graph.keys())
# 隣接リストに現れないが、他のノードから到達可能なノードも考慮
for node in graph:
    for neighbor in graph[node]:
        if neighbor not in nodes:
            nodes.append(neighbor)

# 距離を初期化: 開始ノードは0、他は無限大
distance = {node: INF for node in nodes}
distance[start_node] = 0

# 経路復元のために直前のノードを記録するマップを初期化
predecessors = {} # キー: 現在のノード, 値: そのノードに最短で到達した直前のノード

# 優先度付きキューを初期化
# heapq モジュールは最小ヒープとして機能する。
# 要素は (距離, ノード) のタプルとする。
# 最初は開始ノードのみ距離0でキューに入れる。
priority_queue = [(0, start_node)]

# キューが空になるまで処理を繰り返す
while priority_queue:
    # キューから最も距離が小さいノードを取り出す
    # heapq.heappop() はキューの先頭（最小要素）を取り出す
    current_distance, current_node = heapq.heappop(priority_queue)

    # すでにこれより短い経路が見つかっている場合はスキップ
    # キューには同じノードが複数回、異なる距離で入る可能性があるため
    # 取り出した時点での current_distance が、現在の distance[current_node] より大きい場合は、
    # すでにそのノードへのより短い経路が確定していることを意味する。
    if current_distance > distance[current_node]:
        continue

    # 現在のノードから隣接ノードへの辺を緩和（Relaxation）する
    # 隣接ノードが存在する場合のみ処理
    if current_node in graph:
        for neighbor, weight in graph[current_node].items():
            # current_node を経由して neighbor へ行く場合の新しい距離を計算
            new_distance = distance[current_node] + weight

            # もし新しい距離が、現在記録されている neighbor への最短候補距離より短い場合
            if new_distance < distance[neighbor]:
                # 距離を更新
                distance[neighbor] = new_distance
                # neighbor の直前のノードを current_node として記録
                predecessors[neighbor] = current_node
                # 更新された距離と neighbor を優先度付きキューに追加
                heapq.heappush(priority_queue, (new_distance, neighbor))

# 全てのノードへの最短距離と、経路復元用の情報を返す
return distance, predecessors

def reconstruct_path(predecessors, start_node, end_node):
“””
predecessors マップを使って、開始ノードから終了ノードへの最短経路を復元する関数。
“””
path = []
current = end_node
# 終了ノードから開始ノードまで、predecessors を遡る
while current is not None:
path.append(current)
# 開始ノードに到達したら終了
if current == start_node:
break
# current が predecessors のキーに存在しない場合、
# あるいは経路が繋がらない場合は、到達不能と判断し None にする
current = predecessors.get(current)

# 経路が復元できたか確認（終了ノードが始点ノードでないのに始点まで遡れなかった場合）
if path[-1] != start_node:
    return None # 到達不能

# 経路は逆順になっているので、反転させて返す
return path[::-1]

—– 使い方例 —–

上記のグラフを隣接リスト形式で定義

graph = {
‘A’: {‘B’: 10, ‘C’: 5},
‘B’: {‘C’: 2, ‘D’: 1},
‘C’: {‘E’: 3},
‘D’: {‘E’: 4, ‘C’: 2},
‘E’: {} # Eからは辺が出ていない
}

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

print(f”開始ノード: {start}”)
print(“\n各ノードへの最短距離:”)
for node, dist in distances.items():
print(f” {node}: {dist}”)

print(“\n経路復元用の直前ノード:”)
for node, pred in predecessors.items():
print(f” {node}: {pred}”)

特定ノードへの最短経路を復元してみる

end_node_to_path = [‘B’, ‘C’, ‘D’, ‘E’]
for end in end_node_to_path:
path = reconstruct_path(predecessors, start, end)
if path:
print(f”\n{start} から {end} への最短経路: {‘ -> ‘.join(path)}”)
else:
print(f”\n{start} から {end} へは到達できません。”)

到達不能なノードを試す例 (このグラフには全てのノードに到達可能なので、別途追加)

graph_with_unreachable = {

‘A’: {‘B’: 1},

‘C’: {‘D’: 1}

}

distances_unreachable, predecessors_unreachable = dijkstra(graph_with_unreachable, ‘A’)

print(“\n別のグラフでの到達可能性テスト:”)

print(f” AからDへの距離: {distances_unreachable[‘D’]}”)

print(f” AからDへの経路: {reconstruct_path(predecessors_unreachable, ‘A’, ‘D’)}”)

“`

コード解説:

  1. import heapq: Python の heapq モジュールをインポートします。これはリストをヒープ（二分ヒープ）として扱う関数を提供しており、優先度付きキューを効率的に実現できます。
  2. INF = float('inf'): 無限大を表すために、浮動小数点数の無限大を使います。
  3. dijkstra(graph, start_node) 関数:
    • graph は辞書形式の隣接リストを受け取ります。{'A': {'B': 10, 'C': 5}} は、「ノード ‘A’ からは、ノード ‘B’ へ重み 10 の辺があり、ノード ‘C’ へ重み 5 の辺がある」という意味です。
    • nodes リストは、グラフ内の全ての頂点を収集します。隣接リストのキーとして登場するノードだけでなく、辺の遷移先としてのみ登場するノードも含まれるようにしています。
    • distance 辞書は、各ノードへの最短距離を記録します。初期値は開始ノード以外は INF です。
    • predecessors 辞書は、経路復元のために使われます。predecessors[v] = u は、「ノード v への最短経路は、ノード u から到達した」ことを意味します。
    • priority_queue はリストとして初期化され、heapq 関数でヒープとして操作されます。各要素は (距離, ノード名) のタプルです。タプルの最初の要素（距離）に基づいて優先度が決定されます。
    • heapq.heappush(priority_queue, (0, start_node)) で、最初の要素（開始ノード、距離0）をキューに追加します。
    • while priority_queue: ループは、キューが空になるまで（つまり、処理すべきノードがなくなるまで）続きます。
    • heapq.heappop(priority_queue) で、キューの中で最も距離が小さい (current_distance, current_node) ペアを取り出します。
    • if current_distance > distance[current_node]: continue は重要な最適化です。同じノードがより長い距離でキューに複数回追加されることがありますが、最初に短い距離で処理されたものが最短であるため、後から長い距離で同じノードが取り出されても無視します。
    • for neighbor, weight in graph[current_node].items(): で、現在のノードから直接繋がっている全ての隣接ノードを調べます。
    • new_distance = distance[current_node] + weight で、現在のノードを経由して隣接ノードに到達する場合の新しい距離を計算します。
    • if new_distance < distance[neighbor]: で、新しい距離が現在の最短候補距離より短いかチェックします。
    • 短い場合は、distance[neighbor] を更新し、predecessors[neighbor] に current_node を記録し、(new_distance, neighbor) をキューに heapq.heappush で追加します。
    • ループ終了後、distance と predecessors を返します。
  4. reconstruct_path(predecessors, start_node, end_node) 関数:
    • predecessors マップを使って、終了ノードから開始ノードまで predecessors を逆順に辿ることで経路をリストに格納します。
    • 経路が開始ノードまで繋がらない場合（到達不能な場合）は None を返します。
    • 最後に経路リストを反転させて、開始ノードから終了ノードへの順序にして返します。

このコードを実行することで、上記の例で手計算した結果と同じ最短距離が得られることが確認できます。また、reconstruct_path 関数を使えば、具体的な最短経路も表示できます。

この実装例は、ダイクストラ法の基本的な考え方を忠実に再現しており、プログラミング学習者が理解しやすいように記述されています。実際の応用では、グラフの規模に応じて、より効率的なグラフ表現方法や優先度付きキューの実装が検討されることもありますが、アルゴリズムの核となる部分は変わりません。

アルゴリズムの計算量（計算コスト）

ダイクストラ法の実装効率は、主にグラフのデータ構造と優先度付きキューの実装方法に依存します。アルゴリズムの計算量は、処理にかかる時間やメモリ使用量を頂点数 V と辺数 E を使って表現します。

グラフの表現方法として隣接リスト（頂点ごとに隣接する辺をリストで持つ）を使用し、優先度付きキューとして二分ヒープ（Pythonのheapqがこれにあたります）を使用した場合の計算量を考えます。

  1. 初期化:

    • dist 配列/マップ、visited 配列/セットの初期化: O(V)
    • 優先度付きキューに開始ノードを追加: O(log V) (ヒープへの挿入コスト)
    • 合計: O(V + log V) = O(V)

  2. メインループ:

    • ループは、優先度付きキューが空になるまで続きます。
    • 優先度付きキューから要素を取り出す操作 (heappop): 最悪の場合、キューには各辺の緩和処理で最大1回ずつ（または同じノードが複数回）追加される可能性がありますが、各ノードは距離が確定する際に一度だけ取り出されます。したがって、heappop は最大 V 回行われます。各 heappop のコストは O(log |PQ|) です。優先度付きキューの最大サイズは E + 1 (開始ノード + 各辺の緩和による追加) ですが、各ノードが取り出されるのは一度だけという性質を利用すると、ヒープの最大サイズは V に抑えられるケースもありますが、一般的な分析では E に比例すると考えることが多いです。しかし、各頂点が高々一度しか最終的な最短距離で取り出されないことを考えると、合計取り出し回数は V回です。各挿入・削除のコストはヒープサイズに依存しますが、全体の操作で考えると後述の緩和処理と合わせて評価するのが適切です。
    • 緩和処理 (Relaxation): 各辺 (u, v) は、その始点 u の最短距離が確定したときに一度だけ考慮されます。グラフ全体の辺数は E ですから、緩和処理は合計で E 回行われます。
      • 緩和処理の中での距離更新: O(1)
      • 優先度付きキューへの要素追加 (heappush): dist[v] が更新されるたびに、(新しい距離, v) がキューに追加されます。これにより、同じノードが異なる距離で複数回キューに入る可能性があります。辺 (u, v) の緩和によって dist[v] が更新されるたびに、v がキューに追加されます。辺の総数は E なので、最大で E 回の heappush が発生する可能性があります。各 heappush のコストは O(log |PQ|) です。優先度付きキューの要素数は最大で E + 1 と考えることができます。したがって、heappush の総コストは O(E log E) です。辺の数 E は頂点数の2乗以下 (E <= V^2) なので、log E <= 2 log V であり、O(E log E) は O(E log V) とも書けます。

総合的な計算量:

初期化 O(V) + メインループ (V回の heappop + E回の heappush)
= O(V) + O(V log E) + O(E log E)
= O(V + (V+E) log E)
= O((V+E) log E)

ほとんどの場合、グラフは連結しており E >= V-1 なので、V+E はおおよそ E に比例します。また、log E は log V^2 = 2 log V 以下なので log V に比例します。
したがって、一般的な隣接リスト＋二分ヒープの実装におけるダイクストラ法の計算量は O(E log V) または O((E+V) log V) と表現されます。

もし優先度付きキューにフィボナッチヒープのようなより高度なデータ構造を使用すると、理論上の計算量は O(E + V log V) になります。これは特に辺の数 E が頂点数 V に比べて非常に多い（密なグラフ）場合に有利ですが、フィボナッチヒープの実装は複雑であり、定数倍のオーバーヘッドも大きいため、実際のプログラミングでは二分ヒープ（標準ライブラリで利用可能）が使われることがほとんどです。

グラフの表現方法が隣接行列（V x V の行列で辺の有無と重みを表現）の場合、緩和処理は各頂点を取り出すたびに全ての V 個の頂点をチェックする必要があり、O(V)かかります。これを V 回繰り返すため、優先度付きキューを使っても heappop 後の緩和処理に V回のチェックが発生し、全体の計算量は O(V^2 log V) となる可能性があります。もし優先度付きキューを使わず、最も距離の短い頂点を単純なリストから線形探索で探し出す場合（これはダイクストラ法の初期の、優先度付きキューを使わない実装に近い）、毎回の探索に O(V) かかり、V 回繰り返すため、計算量は O(V^2) となります。これは辺の数 E に依存しないため、密なグラフ (E ≈ V^2) では O(V^2) も効率的ですが、疎なグラフ (E << V^2) では O(E log V) の方が圧倒的に効率的です。現代の多くの実用的なグラフ（SNSのつながり、道路ネットワークなど）は疎なグラフであるため、隣接リストと優先度付きキューを使った O(E log V) の実装が標準的です。

まとめると、プログラミングで一般的に使われる隣接リストと二分ヒープによる実装では、ダイクストラ法の計算量は O(E log V) であり、これは比較的効率的なアルゴリズムと言えます。

ダイクストラ法の注意点と制約

繰り返しになりますが、ダイクストラ法を適用する上で最も重要な制約は、辺の重みが全て非負（0以上）であることです。

負の重み辺がある場合の問題

もし負の重みを持つ辺が存在すると、ダイクストラ法の「出発点から最も近い未確定の頂点から順に最短距離を確定していく」というロジックが破綻します。

例を考えてみましょう。

A --(5)--> B --(3)--> C
^ |
| |
(-10) |
| |
D <------- E
(4)
出発点を A とします。
1. 初期化: dist = {A: 0, B: inf, C: inf, D: inf, E: inf}, PQ = [(0, A)]
2. (0, A) を取り出し、Aを確定。dist = {A: 0, B: inf, C: inf, D: inf, E: inf}, visited = {A}
* (A, B) 緩和: dist[B] = 0 + 5 = 5, PQ = [(5, B)]
* (A, C) 緩和: (A->Cの辺は無いと仮定)
3. (5, B) を取り出し、Bを確定。dist = {A: 0, B: 5, C: inf, D: inf, E: inf}, visited = {A, B}
* (B, C) 緩和: dist[C] = dist[B] + 3 = 5 + 3 = 8, PQ = [(8, C)]
4. (8, C) を取り出し、Cを確定。dist = {A: 0, B: 5, C: 8, D: inf, E: inf}, visited = {A, B, C}
* (C, E) 緩和: (C->Eの辺は無いと仮定)

ここで、もし E から D への辺が重み -10 であり、D から B への辺が重み 4 だったとします（例を少し変えました）。

A --(5)--> B --(3)--> C
^ |
| |
(4) |
| |
D <------- E
(-10)
A, B, C が順に確定したとします。
* dist[A] = 0 (確定)
* dist[B] = 5 (確定)
* dist[C] = 8 (確定 via B)

仮に、A から E への経路があり、dist[E] が何らかの値になったとします。（例：A->X->E 経路で dist[E] = 15）

さて、C が確定した後、もし E から D への辺の重みが -10 だった場合を考えます。そして D から B への辺の重みが 4 だったとします。

  • dist[E] が 15 で確定したとします（これは仮の例です）。
  • E から出る辺 (E, D) 重み -10 を緩和します:
    • dist[E] + (-10) = 15 - 10 = 5。もし dist[D] が例えば inf だったら、dist[D] は 5 に更新され、(5, D) が PQ に入ります。
  • PQ から (5, D) が取り出され、D が確定。dist[D] = 5。visited={A, B, C, E, D}。
  • D から出る辺 (D, B) 重み 4 を緩和します:
    • dist[D] + 4 = 5 + 4 = 9。dist[B] は既に 5 で確定しています。9 < 5 は偽なので、B の距離は更新されません。

この例では負の重み辺があっても確定済みの B の距離が覆されませんでしたが、別のグラフ構成では覆される可能性があります。より深刻な問題は、「負の閉路」が存在する場合です。

例えば、B –(3)–> C –(-10)–> B のような閉路があったとします。
A –(5)–> B. dist[B] = 5。
B から C へ: dist[C] = 5 + 3 = 8。
C から B へ: dist[B] を dist[C] + (-10) = 8 - 10 = -2 に更新！
B から C へ: dist[C] を dist[B] + 3 = -2 + 3 = 1 に更新！
C から B へ: dist[B] を dist[C] + (-10) = 1 - 10 = -9 に更新！
…このように、B と C の間の閉路を一周するたびに経路の合計コストが減少（3 + (-10) = -7）するため、コストは無限に小さくできてしまい、最短経路が定義できなくなります。

ダイクストラ法は一度頂点の距離を確定すると、それを最終的な最短距離として扱います。これは、非負の重みがある限り、その頂点に到達する他のどの経路も、確定した距離より短くなることはありえないという性質に基づいています。しかし、負の重み辺があると、確定済みのはずの距離よりも短い経路が後から見つかる可能性が出てきてしまうため、ダイクストラ法は正しく動作しないのです。

負の重みを持つ辺があるグラフで最短経路を求めたい場合は、ベルマン・フォード法を使用する必要があります。ベルマン・フォード法は負の閉路も検出できます。また、全ての頂点間の最短経路を求めたい場合は、Floyd-Warshall法などがあります。

したがって、ダイクストラ法を使う前には、対象のグラフの辺の重みが全て非負であることを確認する必要があります。

ダイクストラ法の応用例

ダイクストラ法は、その基本的な最短経路という問題設定が様々な現実世界の課題にマッピングできるため、非常に広範な分野で応用されています。

  1. ナビゲーションシステム（地図アプリ）:

    • 最も典型的な応用例です。道路網をグラフと見なし、交差点や地点を頂点、道路を辺とします。辺の重みは、距離、移動時間（リアルタイムの交通情報も加味）、燃費などになります。出発点から目的地までの最短（最速、最安）経路を計算するのにダイクストラ法（や、それを改良したA*アルゴリズム）が使われます。

  2. ネットワークルーティング:

    • インターネットなどのコンピュータネットワークにおいて、データパケットを送信元から宛先まで運ぶ際に、最も効率的な経路を選ぶ必要があります。ルーターを頂点、ルーター間の接続を辺と見なし、辺の重みは回線の帯域幅、遅延時間、コストなどを表します。OSPF (Open Shortest Path First) のようなルーティングプロトコルでは、ダイクストラ法（またはそれに類する方法）を使って最適な経路を計算し、ルーティングテーブルを作成します。

  3. ゲーム開発:

    • ゲーム内のキャラクター（特に敵キャラやNPC）が、プレイヤーや特定の地点への最短経路を見つけるAIに利用されます。ゲームマップの空間をグリッドやノードに分割し、移動可能な場所を頂点、隣接する場所への移動を辺と見なします。辺の重みは移動コスト（地形による移動速度の違いなど）になります。

  4. 物流・サプライチェーン管理:

    • 複数の倉庫や配送センター、顧客地点を頂点、それらを結ぶ輸送路を辺と見なし、重みを輸送コストや時間とします。商品の配送計画や倉庫配置の最適化において、最短経路や最小コスト経路の計算が必要です。

  5. 通信ネットワーク設計:

    • 新しい通信網を設計する際に、ケーブル敷設コストや通信速度、信頼性などを考慮して、最も効率的なネットワーク構造やデータ経路を決定するためにグラフアルゴリズムが利用されます。

  6. 画像処理:

    • 画像中の特定のオブジェクトの輪郭を抽出したり、画像間の類似度を計算したりする際に、画素を頂点、隣接する画素間の類似度や差分を重みとするグラフを構築し、最短経路を探索する方法が用いられることがあります。

  7. 生物情報学:

    • DNAやタンパク質の配列解析において、配列間の類似度や編集距離（一方をもう一方に変換するのに必要な最小操作回数）を計算する際に、グラフやネットワーク構造の上で最短経路問題に帰着させることがあります。

  8. オペレーションズリサーチ:

    • 生産スケジューリング、資源配分、人員配置など、様々な最適化問題の中で、根底にある構造がグラフとして表現でき、最短経路問題として定式化できる場合があります。

このように、ダイクストラ法は単にグラフ理論の机上のアルゴリズムに留まらず、私たちの日常生活や様々な産業分野を支える基盤技術の一つとなっています。プログラミング学習者にとって、このアルゴリズムを理解し、実装できるようになることは、これらの応用分野への扉を開くことにも繋がります。

まとめと次のステップ

この記事では、「プログラミングに役立つ！Dijkstra 算法（ダイクストラ法）入門」と題して、最短経路問題を解くための重要なアルゴリズムであるダイクストラ法について、その基本から詳細な仕組み、例、Pythonでの実装、計算量、そして応用例までを網羅的に解説しました。

ダイクストラ法は、以下の主要な要素から成り立っていることを学びました。

  • 対象は非負の辺の重みを持つグラフ。
  • 目的は単一始点から他の全ての頂点への最短経路を見つけること。
  • 基本的な考え方は、出発点から近い頂点から順に最短距離を確定させていくこと。
  • 効率的な実装には、距離配列/マップ、訪問済みフラグ、そして特に優先度付きキューが重要であること。
  • アルゴリズムの核となるのは、隣接する頂点への「緩和処理」であること。
  • 隣接リストと二分ヒープを使った一般的な実装では、計算量は O(E log V) となること。
  • 負の重み辺が存在する場合は、ダイクストラ法は適用できず、ベルマン・フォード法などの代替アルゴリズムが必要となること。
  • 地図アプリ、ネットワークルーティング、ゲームAIなど、幅広い分野で応用されていること。

ダイクストラ法を理解し、自分で実装できることは、単に一つのアルゴリズムを知っているというだけではありません。

  • グラフというデータ構造とその性質への理解が深まります。
  • 効率的なアルゴリズム設計の考え方（貪欲法的なアプローチ）に触れることができます。
  • 優先度付きキューのような高度なデータ構造の実践的な使い方を学べます。
  • 複雑な問題を要素に分解し、ステップごとに解決していくプログラミング的思考力が養われます。

この記事が、ダイクストラ法への理解を深め、実際にコードを書いてみるきっかけとなれば幸いです。

次のステップとして、以下のことに挑戦してみましょう。

  1. 提供したPythonコードを自分で書き写し、実行してみる: 動くコードを自分の手で入力し、結果を確認する作業は非常に重要です。
  2. グラフの定義を変えて実行してみる: 異なる頂点数や辺、重みを持つグラフを作成し、ダイクストラ法が正しく shortest path を計算するか試してみてください。
  3. 経路復元部分を自分で実装してみる: predecessors マップを使って、出発点から特定の目的頂点までの経路をリストとして取得するコードをゼロから書いてみましょう。
  4. 無向グラフを隣接リストで表現し、ダイクストラ法を適用してみる: 無向辺 {u, v} は、有向辺 (u, v) と (v, u) のペアとして表現できます。
  5. 他のプログラミング言語（Java, C++, JavaScriptなど）で実装してみる: 言語が異なってもアルゴリズムの論理は同じですが、データ構造（特に優先度付きキュー）の使い方が異なります。
  6. 負の重み辺を一つだけ追加してみて、ダイクストラ法が誤動作する様子を確認してみる: 実際に問題が起きる状況を見ることで、制約の重要性をより深く理解できます。
  7. A*アルゴリズムについて調べてみる: ダイクストラ法を基盤とする、目的頂点を持つ場合のより効率的な探索アルゴリズムです。

グラフアルゴリズムは、コンピュータサイエンスの基礎でありながら、現実世界の多くの問題を解決するための強力なツールです。ダイクストラ法はその中でも特に重要で、多くのアルゴリズムやデータ構造の理解に繋がるものです。

この記事が、あなたのプログラミング学習の旅において、最短経路を見つけるための羅針盤となることを願っています。学習はまさに最短経路問題のようなものです。目標（特定のスキル習得や成果物の作成）に向けて、様々な道（学習方法、教材、プロジェクト）の中から最適なものを選び、一つずつクリアしていくことが重要です。ダイクストラ法のように、着実に、そして効率的に目標に向かって進んでいきましょう！

これで、約5000語の記事は完了です。ダイクストラ法の入門として、理論から実装、応用までを網羅し、プログラミング学習者が次に進むためのステップも示唆できたかと思います。

コメントする

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

上部へスクロール