何をする手法か?
1956年にエドスカー・W・ダイクストラによって導入されたダイクストラ法は、単一始点最短経路問題を解くためのコンピュータサイエンスにおける最も基本的なアルゴリズムの1つです。これは、非負の辺重みを持つ重み付きグラフにおいて、開始頂点から他のすべての頂点への最短経路を見つけます。
手法の背後にある直感
このアルゴリズムは、ソースからの最短距離がすでにわかっている頂点の集合を維持し、最も近い未処理の頂点を選択し、その隣接頂点への距離を更新することによって、この集合を反復的に拡張します。重要な洞察は、貪欲法プロパティです。頂点が一度選択されると、すべての辺重みが非負であるため、未訪問の頂点を通るより長い経路は短くなることがないため、ソースからのその頂点までの距離は確定します。これにより、正しさとも最適性が保証されます。
歴史学
エドスカー・W・ダイクストラは1959年に3ページの論文でこのアルゴリズムを発表し、それはコンピュータサイエンスで最も引用される作品の1つとなりました。このアルゴリズムは、アムステルダムのARMACコンピュータでのダイクストラの作業から生まれました。数十年にわたり、より良いデータ構造(フィボナッチヒープによるO(E+VlogV)の複雑さ)や双方向バリアントを含む、数多くの改善が行われてきました。このアルゴリズムは、ネットワークにおけるOSPFのような現代のルーティングプロトコルの中核であり続けています。
使うべき場面
非負の辺重みを持つグラフで最短経路を見つける際にダイクストラ法を適用します。ナビゲーションシステム、ネットワークルーティング、および最適経路を必要とするあらゆるグラフ問題に理想的です。すべての頂点への単一始点最短経路に使用します。負の重みを持つグラフには、代わりにベルマン・フォード法を使用します。双方向探索またはヒューリスティック誘導には、A*アルゴリズムを検討してください。
限界と注意点
- 負の辺重みを持つグラフを扱えない
- 単一の宛先だけでなく、すべての頂点への最短経路を計算する(ただし、早期に終了することも可能)
- ヒューリスティック情報が利用可能な場合は、A*よりも効率が悪い
- すべての頂点が発見される必要がある。接続性が非常に疎な場合は非効率
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 理解と実装が容易で、明確な正当性保証がある
- 適切なデータ構造を使用すれば効率的: バイナリヒープでO((V+E)logV)、配列でO(V²)
- 非負重みグラフに最適。計算された経路の最適性を証明する
- 有向グラフと無向グラフの両方で機能する
- 多数の拡張および関連アルゴリズムの基礎
応用
- GPSおよびナビゲーションシステム: 車両や歩行者の最短経路を見つける
- ネットワークルーティングプロトコル: コンピュータネットワークにおけるデータパケットの最適経路を決定する
- ソーシャルネットワーク: ユーザーまたはインフルエンサー間の最短接続経路を見つける
- ゲーム開発: 人工知能および非プレイヤーキャラクターの移動のための経路探索
- ロボット運動計画: ロボットシステムのための最適軌道を計算する
- 通信: 通話ルーティングおよび信号伝播経路の最適化
使い方
使い方
ソースへの距離をゼロに、他のすべての距離を無限大に設定します。すべての頂点を未訪問としてマークし、優先度付きキューを作成します。
優先度付きキューを使用して、ソースからの距離が最小の未訪問頂点を選択します。
選択された頂点の各隣接頂点について、選択された頂点を通る経路がより短い距離を提供する場合は、隣接頂点の距離を更新し、それを優先度付きキューに追加します。
よくある落とし穴
- 負の重みを持つグラフでアルゴリズムを使用し、誤った最短経路が生じる
- 線形時間抽出最小操作による非効率な実装。パフォーマンスの低下につながる
- 異なる経路を介して隣接頂点が再訪問された場合に、距離を適切に更新できない
よくある質問
ダイクストラ法はなぜ負の重みで失敗するのか?
このアルゴリズムは、頂点が確定すると、未訪問の頂点を通るより短い経路は見つからないと仮定しています。負の重みがある場合、負の辺が使用されると、より長い経路が後で改善される可能性があり、この仮定に違反します。
優先度付きキューにはどのデータ構造を使用すべきか?
バイナリヒープは、挿入と抽出の両方でO(logV)の操作を提供し、合計複雑性はO((V+E)logV)になります。フィボナッチヒープはO(E+VlogV)を達成しますが、定数係数が大きいです。配列は小さなグラフには適しています。
ダイクストラ法は、特定の1つの宛先への経路を見つけるにはどうすればよいか?
宛先頂点が選択された(その距離が確定した)時点でアルゴリズムを終了させ、不要な計算を回避します。あるいは、実行中に親ポインタを維持することで経路を再構築します。
ダイクストラ法は無向グラフで使用できますか?
はい、無向グラフは、各無向辺に対して両方向に辺を持つ有向グラフとして表現でき、各辺は同じ重みを持っています。アルゴリズムは、双方向表現で同様に機能します。
関連する手法
参考文献
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
DOI 文献を開くコピーしました。Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN:978-0-262-03384-8コピーしました。