ダイクストラ法とは
ダイクストラ法は、グラフ理論において、ある始点から他のすべての頂点への最短経路を、辺の重みが非負である場合に効率的に見つけるためのアルゴリズムです。
※「非負」とは、ある対象が負の値（マイナス）でない、0以上であることです。
ダイクストラ法の概要と目的
ダイクストラ法（Dijkstra’s Algorithm）は、オランダの計算機科学者エドガー・ダイクストラによって考案された、単一始点最短経路問題を解くための代表的なアルゴリズムです。このアルゴリズムは、重み付きグラフ（各辺に移動コストや距離などの数値が割り当てられたグラフ）において、指定された始点から他のすべての頂点への最短経路とそのコスト（距離）を計算することを目的とします。
ただし、このアルゴリズムは、辺の重みが非負であるグラフにのみ適用可能です。負の重みを持つ辺が存在する場合、ベルマン・フォード法などの別のアルゴリズムを使用する必要があります。
日常生活における最短経路検索（カーナビゲーションシステムや地図アプリでの経路案内など）の基盤技術としても広く利用されています。
ダイクストラ法の仕組み
ダイクストラ法は、貪欲法（Greedy Algorithm）の一種であり、始点から最も近い未訪問の頂点を順に確定していくことで最短経路を探索します。アルゴリズムの基本的な流れは以下の通りです。
- 初期化:
- すべての頂点について、始点からの仮の最短距離を無限大に設定します。
- 始点自身の仮の最短距離は0に設定します。
- すべての頂点を「未訪問」としてマークします。
- 優先度キュー（または最小ヒープ）に、(距離, 頂点) のペアを格納し、始点を初期値として追加します。
- 探索の繰り返し:
- 優先度キューから、最も距離が小さい未訪問の頂点 u を取り出します。このとき取り出された頂点 u への距離は、始点からの最短距離として確定します。
- 頂点 u を「訪問済み」としてマークします。
- もし、取り出した頂点 u への距離が、既に確定している最短距離よりも大きい場合は、この頂点への経路は最適なものではないため、スキップします（これは優先度キューに同じ頂点が異なる距離で複数入る場合があるため）。
- 頂点 u に隣接するすべての未訪問の頂点 v について、以下の処理を行います。
- 始点から頂点 u を経由して頂点 v に到達する新しい経路の距離を計算します。これは、「始点から u までの確定距離 + u から v への辺の重み」で表されます。
- もし、この新しい経路の距離が、現在記録されている頂点 v への仮の最短距離よりも小さければ、頂点 v の仮の最短距離を更新し、優先度キューに (新しい距離, 頂点 v) を追加します。
- 終了条件:
- 優先度キューが空になるか、またはすべての頂点への最短距離が確定するまで、ステップ2を繰り返します。
最終的に、各頂点に記録された仮の最短距離が、始点からの確定された最短距離となります。また、最短経路を復元するために、各頂点への最短経路を更新する際に、その直前の頂点（親ノード）を記録しておくのが一般的です。
ダイクストラ法の計算量
ダイクストラ法の計算量は、グラフの表現方法や優先度キューの実装によって異なります。
- 隣接行列（Adjacency Matrix） を使用し、優先度キューを単純な配列で実装した場合:
- 各ステップで未訪問の頂点の中から最小距離を探すのに O(∣V∣) 時間かかります。これを ∣V∣ 回繰り返すため、合計で O(∣V∣2)
- 隣接リスト（Adjacency List） を使用し、二分ヒープ（Binary Heap） を優先度キューとして実装した場合:
- 頂点の取り出し: O(log∣V∣)
- 辺のリラックス（距離の更新）: O(log∣V∣)
- 全体として O((∣V∣+∣E∣)log∣V∣)
グラフの辺の数が少ない（疎なグラフ）場合は二分ヒープ、辺の数が多い（密なグラフ）場合は隣接行列を使った実装が有利になる傾向があります。
ダイクストラ法の例
以下のような重み付きグラフを考え、頂点Aから各頂点への最短経路を求めます。
- 初期化:
- A: 0, B: ∞, C: ∞, D: ∞
- 未訪問: {A, B, C, D}
- 優先度キュー: {(0, A)}
- 1回目:
- キューから (0, A) を取り出す。Aを確定。
- Aの隣接:
- B: 0 + 1 = 1。Bの距離を1に更新。キューに (1, B) を追加。
- C: 0 + 4 = 4。Cの距離を4に更新。キューに (4, C) を追加。
- 確定済: {A}
- 距離: A: 0, B: 1, C: 4, D: ∞
- キュー: {(1, B), (4, C)}
- 2回目:
- キューから (1, B) を取り出す。Bを確定。
- Bの隣接:
- C: 1 + 2 = 3。Cの現在の距離4より小さいので、3に更新。キューに (3, C) を追加。
- D: 1 + 5 = 6。Dの距離を6に更新。キューに (6, D) を追加。
- 確定済: {A, B}
- 距離: A: 0, B: 1, C: 3, D: 6
- キュー: {(3, C), (4, C), (6, D)} ※(4, C)は古いCへの経路なので、後で取り出されるがスキップされる
- 3回目:
- キューから (3, C) を取り出す。Cを確定。
- Cの隣接:
- D: 3 + 1 = 4。Dの現在の距離6より小さいので、4に更新。キューに (4, D) を追加。
- 確定済: {A, B, C}
- 距離: A: 0, B: 1, C: 3, D: 4
- キュー: {(4, C)(スキップ), (4, D), (6, D)(スキップ)}
- 4回目:
- キューから (4, D) を取り出す。Dを確定。
- Dに未訪問の隣接はない。
- 確定済: {A, B, C, D}
- 距離: A: 0, B: 1, C: 3, D: 4
- キュー: 空
結果として、始点Aからの各頂点への最短距離は以下のようになります。
- A → A: 0
- A → B: 1
- A → C: 3
- A → D: 4
ダイクストラ法の応用
ダイクストラ法は、以下のような分野で幅広く利用されています。
- 経路探索アルゴリズム: カーナビゲーションシステム、地図アプリ、物流最適化。
- ネットワークルーティング: データパケットがネットワーク内で最短経路で伝送されるようにルーティングプロトコルで利用されます（例: OSPF）。
- リソース割り当て: 最短時間でタスクを完了するための資源配分。
- AIゲーム開発: ゲームキャラクターの移動経路探索。
- 金融モデリング: 最適な取引経路の特定など。
ダイクストラ法は、そのシンプルさと効率性から、グラフにおける最短経路問題の基本的な解決策として、現代のITシステムにおいて不可欠なアルゴリズムの一つです。
関連用語
お問い合わせ
システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
