![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
このページは競技プログラミングに興味のある方向けにダイクストラ法を簡単に説明するページです
有向グラフ上の二つのノードを結ぶ最短経路を求める手法です
点(ノード)を線(辺)で結んだものを指します
ダイクストラ法は以下の条件が満たされるときによく用いられます
1.各辺にコストが割り当てられ、それは非負である
2.各辺のコストが一定でない(これを「辺に重みがある」などと表現します)
1は必要条件です。非負の重みをもつ辺がある場合はベルマン-フォード法等を用いましょう
2は必要条件ではありませんが、辺に重みが無い場合は幅優先探索で行う方が実装が容易で計算量も少なくて済むのでそちらを使いましょう
ダイクストラ法では各ノードに2つの情報と1つのフラグを付与する必要があります
情報1：スタート地点から各ノードへ移動する「暫定最短距離」
情報2：各ノードへ暫定最短距離で移動する際に直前に経由する「暫定直前経由ノード」
フラグ：更新するノードかどうかを示す「更新フラグ」
(暫定最短距離だとか、暫定直前経由ノードとかは適当に名づけただけです)
この3つを用意したら、以下のステップでスタート地点から終了地点までの最短経路をノード数Vに対してO(V^2)で求めることが出来ます
1.全てのノードの「暫定最短距離」を「-1」に、「更新フラグ」をOFFにする
2.開始ノード(スタート地点)の「暫定最短距離」を0にし「更新フラグ」をONにする
3.「更新フラグ」がONのノードを全列挙するとともに列挙したノードの「更新フラグ」をOFFにします
4.3で列挙した各ノードについて"一つの辺を経由してたどり着くノード"を全て調べ、経由先のノードの「暫定最短距離」について
A.(経由先の「暫定最短距離」) > (経由元のノードの「暫定最短距離」＋ 辺の重み) または 経由先の「暫定最短距離」が-1 の場合
「経由先の暫定最短距離」＝「経由元のノードの「暫定最短距離」＋ 辺の重み」とし、
経由先の「暫定直前経由ノード」を経由元のノードとし、「更新フラグ」をONにする
B.(経由先の「暫定最短距離」) < (経由元のノードの「暫定最短距離」＋ 辺の重み)の場合
とくになにも行いません
5.全てのノードについて「更新フラグ」がOFFであれば、計算終了。そうでないなら3に戻る
(もし、この時すべてのノードの「更新フラグ」がOFFであるにも関わらず「暫定最短距離」が-1のノードが存在するなら連結グラフではない)
これらの操作が終了すると、各ノードにある「暫定最短距離」が開始ノードからそのノードへ行くまでの最短距離に相当し
その経由手順は「暫定直前経由ノード」をさかのぼることで得ることが出来ます
この時「暫定最短距離」が-1であるノードに行くことは出来ません
注：更新フラグをOFFにするのは、列挙した直後です。4の直後に「3で列挙したノードの「更新フラグ」をOFF」
という手順だと、4において3で列挙したノードの「暫定最短距離」が更新された場合に問題が発生します
無向グラフは例えばA, Bの二つのノードに対してA→Bの辺とB→Aの二つの辺があるグラフとみなせますので
そのまんま同じ手法を使ってください
