コンピューターサイエンス上級：アルゴリズムとデータ構造
ダイクストラ法 — 重み付きグラフの最短経路
ダイクストラ法 とは
重み付きグラフでの最短経路問題を解くダイクストラ法を、概念・図・擬似コード・Python 実装・計算量・よくある誤解まで一気通貫で学ぶ。
ダイクストラ法 — 重み付きグラフの最短経路
ダイクストラ法（Dijkstra's algorithm） は、辺に 正の重み（コスト） が付いたグラフで、ある始点 s から各ノードまでの 最短経路長 を求めるアルゴリズムです。1959 年に Edsger W. Dijkstra が発表した古典で、カーナビ・ルーター（OSPF）・配送ルート計算など、現代のあらゆる「最短経路」の心臓部に置かれています。
重みなしグラフは BFS、重み付きグラフは Dijkstra。これが鉄則です。負の重みがあるときは Bellman-Ford や SPFA を選びます。
結論先取り（このレッスンで分かること）
- 問題定義 — 始点
sから終点t（または全ノード）への最短コストを求める - アイデア — 「未確定ノードの中で、現状コストが最小のものを確定する」を繰り返す
- 実装 — 優先度付きキュー（min-heap）で O((n + m) log n)
- 使えない場面 — 負の重みがあるグラフでは正しさが崩れる
問題定義 — BFS との違い
n ノード、辺リスト edges = [(u, v, w), ...] （w >= 0）を受け取り、s から各ノードへの最短コスト配列 dist を返します。到達不能なノードの距離は INF のままです。
このグラフで s -> t の最短コストは s -> A -> B -> C -> t = 1 + 2 + 1 + 3 = 7。「辺の本数が少ない経路」と「コストが小さい経路」は別物なので、BFS では正しく解けません。重みが入った瞬間に、距離レベルでまとめて展開する BFS の前提が崩れるためです。
概念 — 「コスト最小の未確定」を確定する
Dijkstra の本質は 貪欲法 です。各ノードに「現時点で分かっている最短コスト dist[v]」を持たせ、次の手順を繰り返します。
- すべての
dist[v] = INF、ただしdist[s] = 0 - 未確定ノードの中で
distが最小のノードuを取り出し、確定にする uの隣接ノードvについて、dist[u] + w(u, v) < dist[v]ならdist[v]を更新する（緩和、relaxation）- すべて確定するか、未確定の最小が INF になったら終了
ポイントは 「一度確定したノードのコストは二度と更新されない」 こと。これは「正の重み」と「貪欲な選択」から導かれる強い性質で、Dijkstra の正しさを支えています。
負の重みがあると、未確定の中に「もっと小さい遠回り経路」が潜んでいる可能性が生まれ、確定の前提が崩れます。負の重みなら Bellman-Ford を使いましょう。
擬似コード
プレーンテキスト
function dijkstra(n, edges, s):
dist = [INF] * n
dist[s] = 0
pq = min-heap of (cost, node)
push (0, s) to pq
while pq not empty:
(d, u) = pop pq
if d > dist[u]: continue # stale entry
for (v, w) in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
push (nd, v) to pq
return distif d > dist[u]: continue のガードが重要で、ヒープに古いエントリが残っていても無視できます。これによって「decrease-key」を使わない、シンプルで速い実装になります。
Python 実装
Python
import heapq
def dijkstra(n, edges, s):
INF = float("inf")
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w)) # 無向グラフの場合
dist = [INF] * n
dist[s] = 0
pq = [(0, s)] # (cost, node)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist無向グラフを想定して両方向に辺を張っています。有向グラフなら adj[v].append((u, w)) の行を削るだけです。heapq は min-heap なので、最小コストのエントリが必ず先に取れます。
計算量 — なぜ O((n + m) log n)？
各辺は最大 1 回 relax され、その都度ヒープへの push が起きます。push / pop は O(log n) なので、合計は O((n + m) log n)。優先度付きキューを使わない素朴版は O(n^2) で、密グラフ（m ≈ n^2）ではこちらが速いこともあります。
| 実装 | 時間計算量 | 向いている場面 |
|---|---|---|
| 配列で min を線形探索 | O(n^2) | 密グラフ、n 小 |
| バイナリヒープ（heapq） | O((n + m) log n) | 一般的、疎グラフ |
| Fibonacci heap | O(m + n log n) | 理論最適、実装は重い |
空間計算量はいずれも O(n + m)（隣接リスト + dist 配列）。
よくある誤解
1 つ目は 「負の重みでも動く」と思ってしまう こと。動きはしますが結果が間違います。s -> A (3), A -> B (-2), s -> B (2) のような小例で簡単に破綻します。2 つ目は 「heap に push しないで dist だけ更新する」 ミス。一度ヒープから出したノードを再度入れ直さないと、緩和が伝播しません。3 つ目は 「終点 t に着いた瞬間に return しない」 こと。実は 着いた瞬間に return しても正しい のが Dijkstra の便利な性質で、u == t で pop した時点で dist[t] は確定済みです（早期終了の最適化として使えます）。
Dijkstra は 「BFS の重み付き拡張」 と理解すると一気に親しみやすくなります。距離ごとに展開する BFS の
queueを、コスト順に展開するpriority queueに置き換えただけです。
やってみよう
n=5, edges=[(0,1,1),(1,2,2),(0,2,4),(2,3,1),(3,4,3)], s=0でdist = [0,1,3,4,7]になることを手計算- 無向グラフを有向グラフに変えたとき、どこを 1 行直せば対応できるか確認する
- 早期終了版を書く — 終点
tを引数に取り、u == tで pop した瞬間にdist[t]を返す
よくある質問
Q. ダイクストラ法が使えない条件は？
A. 負の重みがある場合は使えません（ベルマンフォード法やジョンソン法を使う）。すべての辺が非負ならダイクストラが O((V+E) log V) で最速です。実装は優先度付きキューで未確定の最小距離ノードを取り出すのが定石です。
Q. BFS との違いは？
A. 辺の重みが全て同じなら BFS が O(V+E) で動き、ダイクストラより速いです。重みが異なるならダイクストラが必要で、計算量は priority queue 分やや重くなります。「重みなし」と「重みあり」で使い分けるのが基本です。
Q. A* 探索とどう違う？
A. ダイクストラは全方向に均等に探索しますが、A* は目的地までの推定値（ヒューリスティック）を加えてゴール方向を優先します。マップ上の経路探索（ゲーム・カーナビ）では A* の方が高速ですが、適切なヒューリスティック設計が鍵です。
次のレッスン
次は 第5章まとめクイズ — グラフ で、重み付きグラフでの最短経路問題を解くダイクストラ法を、概念・図・擬似コード・Python 実装・計算量・よくある誤解まで一気通貫で学ぶ を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- ダイクストラ法 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. ダイクストラ法 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン