ダイクストラ法：非負重みグラフの単一始点最短経路アルゴリズム

主な特徴

このアルゴリズムは貪欲法です。未処理の頂点のうち暫定距離が最小のものを繰り返し選択し、そこから出る辺を緩和します。重要な要素は次のとおりです。

• 頂点と辺：数値の重みを持つノードと接続。
• 非負の重み：正しさを保証するために必要な条件です。
• 暫定距離：実行中に更新される、最短経路の暫定的な推定値です。

動作方法

大まかな手順は次のとおりです。

• 始点の距離を0に初期化し、他のすべての頂点の距離を無限大に設定します。
• 未訪問の頂点のうち、距離が最小のものを選択します。
• 各隣接頂点について、選択した頂点を経由する候補距離を計算し、それがより小さければ更新します。これを「緩和」といいます。
• 選択した頂点を訪問済みにし、到達可能なすべての頂点が処理されるまで繰り返します。

計算量と変種

性能は、最小距離の頂点を選択するために使うデータ構造に依存します。二分ヒープを用いる場合、計算量はおおむね O((V + E) log V) です。フィボナッチヒープでは、理論上 O(E + V log V) まで削減されます。隣接行列を用いる密なグラフでは、O(V2) で実装できます。実用的な実装では、メモリ使用量とオーバーヘッドを理論的な計算量との兼ね合いで選択します。

歴史、用途と制約

1959年にエドガー・W・ダイクストラが発表したことにちなみ名付けられたこのアルゴリズムは、コンピュータ科学の基礎的な手法となりました。主な用途には、GPSやインターネットのルーティングプロトコルにおける最短経路ルーティング、ゲームの経路探索、資源最適化があります。主な制約は負の辺重みを扱えないことです。負の重みや負閉路を考慮する必要がある場合には、ベルマン–フォード法などのアルゴリズムが用いられます。