地図アプリや交通経路の最適化など、私たちの生活に密接に関わる「最短経路問題」を解くアルゴリズムとして、ダイクストラ法は最も有名なものの一つです。
グラフ理論における単一始点最短経路問題を効率的に解くこのアルゴリズムは、実装方法によってO(V²)からO((V+E) log V)まで計算量が変わります。
本記事では、ダイクストラ法の計算量（特にO(V²)）がどこから来るのかを解説するとともに、グラフ理論の基礎・優先度付きキューを使った改良版・単一始点最短経路問題の概要についても詳しく説明します。
ぜひ最後まで読んでみてください。
ダイクストラ法の計算量はO(V²)または O((V+E) log V)（結論）
それではまず、ダイクストラ法の計算量とその理由について解説していきます。
ダイクストラ法の計算量は実装方法によって2種類に分かれます。
基本実装（配列版）ではO(V²)、優先度付きキュー（二分ヒープ）を使った改良版ではO((V+E) log V)となります。
ここでVはグラフの頂点（Vertex）数、Eは辺（Edge）数です。
ダイクストラ法の計算量は「グラフの密度」によって適切な実装を選ぶことが重要です。頂点数Vに対して辺数Eが少ない疎グラフではO((V+E) log V)の優先度付きキュー版が有利で、辺数が多い密グラフではO(V²)の基本版も競争力があります。
O(V²)になる理由（基本実装）
基本実装では、未確定頂点の中から「現在の最短距離が最小の頂点」を毎回線形探索で見つけます。
この最小値探索にO(V)かかり、それをV回繰り返すためO(V²)になります。
基本実装の計算量の内訳
・最小距離頂点の探索：O(V) × V回 = O(V²)
・隣接頂点の距離更新：O(E)（全辺を1回ずつ処理）
・合計：O(V² + E) = O(V²)（E ≦ V²のため）
O((V+E) log V)になる理由（優先度付きキュー版）
優先度付きキュー（二分ヒープ）を使うと、最小距離頂点の取り出しをO(log V)で行えます。
これをV回繰り返す部分がO(V log V)です。
距離の更新（decrease-key操作）はO(log V)で行えるため、E回の更新でO(E log V)です。
合計するとO((V+E) log V)となります。
| 実装方法 | 時間計算量 | 適したグラフ |
|---|---|---|
| 配列による線形探索 | O(V²) | 密グラフ（E ≒ V²） |
| 二分ヒープ（優先度付きキュー） | O((V+E) log V) | 疎グラフ（E ≒ V） |
| フィボナッチヒープ | O(E + V log V) | 理論的に最適・実装複雑 |
空間計算量
ダイクストラ法の空間計算量はO(V+E)です。
グラフの隣接リスト表現にO(V+E)、距離配列と訪問済み配列にO(V)必要です。
優先度付きキューにはO(V)の空間が追加で必要になります。
グラフ理論の基礎とダイクストラ法の前提
続いては、ダイクストラ法を理解するために必要なグラフ理論の基礎と、このアルゴリズムの前提条件について確認していきます。
グラフの基本概念
グラフは「頂点（ノード）」と「辺（エッジ）」で構成されるデータ構造です。
辺に方向がある「有向グラフ」と方向がない「無向グラフ」、辺に重みがある「重み付きグラフ」があります。
ダイクストラ法は重み付き有向グラフ（または無向グラフ）の単一始点最短経路問題を解くアルゴリズムです。
グラフの例：都市間の道路網
頂点：東京、名古屋、大阪、京都
辺（重み＝距離）：東京→名古屋（366km）、名古屋→大阪（190km）など
問題：東京から各都市への最短経路を求めよ
ダイクストラ法の前提条件
ダイクストラ法には重要な前提条件があります。
それは「辺の重みがすべて非負（0以上）であること」です。
負の重みを持つ辺がある場合、ダイクストラ法は正しい最短経路を求められません。
負の重みを扱う場合は、ベルマンフォード法（O(VE)）を使う必要があります。
実際の応用では、距離・時間・コストなど多くの場合は非負であるため、ダイクストラ法が広く適用できます。
単一始点最短経路問題とは
単一始点最短経路問題（Single Source Shortest Path, SSSP）とは、グラフ上の特定の1頂点（始点）から他のすべての頂点への最短経路を求める問題です。
ダイクストラ法はこの問題に対する代表的な解法であり、O(V²)またはO((V+E) log V)で解きます。
すべての頂点間の最短経路を求めたい場合（全対全最短経路問題）には、フロイド・ワーシャル法O(V³)などが使われます。
ダイクストラ法のアルゴリズムと実装
続いては、ダイクストラ法の具体的なアルゴリズムの流れと実装を確認していきます。
アルゴリズムの手順
ダイクストラ法の基本的な手順は以下のとおりです。
① 始点sの距離をdist[s]=0、他すべてをdist[v]=∞とする
② 未確定頂点の集合Qを全頂点で初期化する
③ Qが空になるまで以下を繰り返す
③-1. Qの中でdist[u]が最小の頂点uを取り出す
③-2. uの各隣接頂点vについて、dist[u] + w(u,v) < dist[v]なら dist[v]を更新する
④ すべてのdist[v]が最短距離
Pythonでの実装（優先度付きキュー版）
import heapq
def dijkstra(graph, start):
dist = {v: float(‘inf’) for v in graph}
dist[start] = 0
pq = [(0, start)] # (距離, 頂点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
Pythonのheapqはmin-heapなので、距離を優先度として最小距離頂点を効率的に取り出せます。
この実装の時間計算量はO((V+E) log V)です。
動作の具体例
4頂点のグラフ（A→B:1, A→C:4, B→C:2, B→D:5, C→D:1）でダイクストラ法を適用します。
| ステップ | 確定頂点 | dist[A] | dist[B] | dist[C] | dist[D] |
|---|---|---|---|---|---|
| 初期 | – | 0 | ∞ | ∞ | ∞ |
| 1 | A | 0 | 1 | 4 | ∞ |
| 2 | B | 0 | 1 | 3 | 6 |
| 3 | C | 0 | 1 | 3 | 4 |
| 4 | D | 0 | 1 | 3 | 4 |
AからDへの最短距離は4（A→B→C→D）と求まります。
ダイクストラ法の応用と関連アルゴリズム
続いては、ダイクストラ法の実際の応用場面と、関連する最短経路アルゴリズムとの比較を確認していきます。
実際の応用場面
ダイクストラ法は非常に広い分野で応用されています。
ナビゲーションシステム（カーナビ・Googleマップ）では、交差点を頂点・道路を辺・距離や時間を重みとするグラフにダイクストラ法を適用しています。
ネットワークルーティングプロトコルのOSPF（Open Shortest Path First）はダイクストラ法をベースにしており、インターネットの経路制御に使われています。
ゲームのAIにおけるキャラクターの経路探索にも、ダイクストラ法やその改良版であるA*アルゴリズムが使われています。
ダイクストラ法は理論的な美しさと実用的な効率を兼ね備えた、最も重要なアルゴリズムの一つです。
ベルマンフォード法との比較
ベルマンフォード法は負の重みを持つ辺にも対応できますが、時間計算量はO(VE)とダイクストラ法より遅いです。
また負の重みを持つ閉路（負閉路）の検出にも使えます。
| 比較項目 | ダイクストラ法 | ベルマンフォード法 |
|---|---|---|
| 負の重み | 不可 | 可（負閉路以外） |
| 時間計算量 | O((V+E) log V) | O(VE) |
| 負閉路の検出 | 不可 | 可 |
A*アルゴリズムとの関係
A*（エースター）アルゴリズムはダイクストラ法に「ヒューリスティック関数h(v)」を加えた改良版です。
h(v)は現在地点vから目標地点までの推定コストを表し、より目標に近い方向を優先的に探索することで探索効率を上げます。
ヒューリスティックが0の場合はダイクストラ法と等価になります。
A*はゲームAIやロボット経路計画で特によく使われます。
まとめ
ダイクストラ法は単一始点最短経路問題を解くアルゴリズムで、基本実装ではO(V²)、優先度付きキューを使った改良版ではO((V+E) log V)の時間計算量です。
辺の重みが非負であることが前提条件であり、この条件が満たされる多くの実問題に適用できます。
グラフが疎か密かによって適切な実装を選ぶことが計算効率の面で重要です。
ナビゲーション・ネットワークルーティング・ゲームAIなど幅広い応用を持つ、現代コンピュータサイエンスにおける最重要アルゴリズムの一つです。
ぜひ実装と応用を通じて、ダイクストラ法の理解を深めてみてください。
