ダイクストラ法

概要

ダイクストラ法は、単一始点最短経路問題のアルゴリズムの一つです。

基本的な考え方は貪欲法です。以上!

 

オーダーは実装方法によって異なり、挑戦数をV、辺の数をEとした時以下のようになります。

  • 深さ優先探索を用いる場合:O(V^2)
  • priority_queueを用いる場合:O(E logV)

DFSだとスタックオーバーフローの可能性もあるので、以下ではpriority_queueの例を掲載します。

制約

コストが負の辺(正確には負の閉路)が存在する場合、このアルゴリズムは使用できないことに注意してください。
負辺を持つグラフの最短経路問題はベルマンフォード法を使用しましょう。

経路復元

探索中に経路を更新する際、その頂点にどの頂点から来たか、一個手前の頂点の情報を保存しておきます。
ゴール側からその情報を辿ることで経路を復元することができます。

ライブラリ

拡張ダイクストラを実装しやすくするために、priority_queueをtupleで実装しています。

関連問題