ダイクストラ法とは？ 10分でわかりやすく解説

最短経路問題を解く代表的なアルゴリズムとして、ダイクストラ法があります。ダイクストラ法は、単一始点最短経路問題において、始点から他のすべての頂点への最短距離と、その経路を求めるための手法です。ただし、正しく使うには「負の重みを扱えないこと」「距離が確定する仕組み」「優先度付きキューを用いた実装方法」といった前提を理解しておく必要があります。本記事では、ダイクストラ法の基本的な考え方から実装の要点、応用時の注意点までを整理して解説します。

ダイクストラ法とは

ダイクストラ法は、重み付きグラフにおける単一始点最短経路問題を解くアルゴリズムです。一般に、始点から各頂点までの最短距離を求めます。経路についても、更新時に前駆（親）情報を記録しておくことで、後から復元できます。

最短経路問題とダイクストラ法の概要

最短経路問題とは、グラフ上で頂点同士を結ぶ経路のうち、辺に設定されたコスト（重み）の合計が最小となるものを求める問題です。交通ルートの探索やネットワークの経路制御、ゲームAIの移動処理など、実務でも幅広く使われています。

ダイクストラ法は、「現時点で最も距離が短い頂点を確定させる」という考え方に基づいて探索を進めます。条件が満たされていれば、この確定結果が後から覆ることはありません。

• 単一始点最短経路を求められる
• 負の重みが含まれないグラフで正しく動作する
• 優先度付きキューを使うと、大規模な疎グラフでも処理しやすい

ダイクストラ法が扱うグラフの条件

ダイクストラ法は、すべての辺の重みが0以上（非負）である重み付きグラフを前提とします。有向グラフ、無向グラフのいずれにも適用できます。

一方で、負の重みを含む場合は距離の確定が成り立たず、正しい結果になりません。そのような場合には、ベルマン–フォード法など別のアルゴリズムを用います。

ダイクストラ法の基本的な考え方

ダイクストラ法は、次の処理を繰り返すことで最短距離を求めます。

未確定の頂点の中から、始点からの暫定距離が最小の頂点を選び、その距離を確定する。確定した頂点から伸びる辺を使って、隣接頂点の暫定距離を更新する。

この手順が正しく機能するのは、すべての辺の重みが非負であることが前提です。

ダイクストラ法のアルゴリズム

ここでは、実装を想定した処理の流れを整理します。

ダイクストラ法の手順

1. 距離配列 dist を用意し、始点 s は dist[s] = 0、それ以外は無限大（十分に大きな値）に設定する
2. 優先度付きキュー（最小ヒープ）に (0, s) を追加する
3. キューから (d, v) を取り出す（d は暫定距離、v は頂点）
4. d が dist[v] と一致しない場合は、古い情報として処理を行わない
5. v から出る各辺 (v → u, 重み w) について、dist[u] > dist[v] + w であれば dist[u] を更新し、(dist[u], u) をキューに追加する
6. キューが空になるまで繰り返す

優先度付きキューでは、同じ頂点が複数回入ることがあります。そのため、距離が一致しないデータを無視する判定を入れるのが一般的です。

ダイクストラ法の計算量

最小ヒープ（優先度付きキュー）を用いた一般的な実装では、各辺の緩和操作とヒープ操作により、計算量はO(E log V)が目安です（疎グラフでは、おおむね O((V+E)logV) と表現されることもあります。Vは頂点数、Eは辺数です）。

配列を使って毎回最小距離の未確定頂点を探す方法では O(V²) となり、頂点数が多い場合は処理時間が増えやすくなります。

ダイクストラ法の実装パターン

• 優先度付きキューを使う方法
  • 疎グラフで特に効果的
  • 実務・競技の双方で一般的
• 配列を使う方法
  • 実装が単純
  • 小規模な問題では十分に実用的

最短距離だけでなく経路も必要な場合は、距離更新時に prev[u] = v のように前駆情報を保存しておき、終点から逆に辿ることで経路を復元できます。

ダイクストラ法の応用と注意点

主な応用例

• 地図・ナビゲーションにおける最短距離や最短時間の探索
• 通信ネットワークでの経路選択（リンクコスト最小）
• 物流における配送経路の最適化
• ゲームでの移動コストを考慮した経路探索
• ロボットの移動計画

始点が固定され、複数の到達先への距離をまとめて求めたい場面で使われることが多い手法です。

他手法との使い分け

ダイクストラ法の制約

• 負の重みを含むグラフでは使用できない
• グラフ規模が大きい場合、メモリや計算時間の影響を受けやすい
• 辺コストが頻繁に変わる環境では再計算が必要になる
• 特定の1点だけを目的とする場合は、A*の方が効率的なこともある

まとめ

ダイクストラ法は、非負重みの重み付きグラフにおいて、始点から各頂点への最短距離と経路を求める基本的なアルゴリズムです。優先度付きキューを用いた実装が一般的で、疎グラフでは効率よく動作します。負の重みを含まないことを確認したうえで使えば、交通、通信、物流、ゲームなど幅広い分野で実用的に利用できます。

よくある質問

ダイクストラ法はどんな問題を解きますか？

非負重み（0以上）の重み付きグラフにおいて、始点から各頂点への最短距離を求める単一始点最短経路問題を解きます。

負の重みがあるとダイクストラ法は使えませんか？

使えません。負の重みがあると距離の確定が正しく行われず、誤った結果になる可能性があります。その場合はベルマン–フォード法などを検討します。

有向グラフと無向グラフのどちらで使えますか？

どちらでも使えます。無向グラフは、各辺を双方向の有向辺として扱うと実装しやすくなります。

ダイクストラ法で「距離が確定する」とは何ですか？

その頂点への距離が、それ以降どの経路を考えてもこれ以上短くならないと保証された状態を指します。非負重みであることが前提です。

優先度付きキューを使う理由は何ですか？

未確定の頂点の中から、最短距離のものを高速に取り出すためです。大規模グラフでも処理時間を抑えられます。

計算量 O((V+E)logV) はいつ成り立ちますか？

最小ヒープなどの優先度付きキューを使って実装した場合の目安です。

最短距離だけでなく経路も求められますか？

求められます。距離更新時に前駆情報を保存しておけば、目的地から逆に辿ることで経路を復元できます。

A*アルゴリズムとダイクストラ法の違いは何ですか？

ダイクストラ法はヒューリスティックを使わず、始点から全体に探索を広げます。A*はゴールまでの見積もりを使い、特定の終点に対して探索を絞れる点が違いです。

辺の重みがすべて1のときはどうなりますか？

その場合（すべての辺の重みが同一の非負値、特に1のとき）は、幅優先探索（BFS）で最短距離を求められ、通常はBFSの方が軽量です。

実務で使う際の注意点はありますか？

負の重みが混ざっていないか、重みの意味が一貫しているか、グラフ規模に対して計算量とメモリが許容範囲かを確認することが重要です。