ダイクストラ法

ダイクストラ法 †

このページは競技プログラミングに興味のある方向けにダイクストラ法を簡単に説明するページです

ダイクストラ法って？ †

有向グラフ上の二つのノードを結ぶ最短経路を求める手法です

グラフって何？ †

点(ノード)を線(辺)で結んだものを指します

どんな時に使うの？ †

ダイクストラ法は以下の条件が満たされるときによく用いられます
1.各辺にコストが割り当てられ、それは非負である
2.各辺のコストが一定でない(これを「辺に重みがある」などと表現します)

1は必要条件です。非負の重みをもつ辺がある場合はベルマン-フォード法等を用いましょう
2は必要条件ではありませんが、辺に重みが無い場合は幅優先探索で行う方が実装が容易で計算量も少なくて済むのでそちらを使いましょう

どういう手順で求めるの？ †

ダイクストラ法では各ノードに2つの情報と1つのフラグを付与する必要があります

情報1：スタート地点から各ノードへ移動する「暫定最短距離」
情報2：各ノードへ暫定最短距離で移動する際に直前に経由する「暫定直前経由ノード」
フラグ：確定したノードかどうかを示す「確定フラグ」

(暫定最短距離だとか、暫定直前経由ノードとかは適当に名づけただけです)

この3つを用意したら、以下のステップでスタート地点から終了地点までの最短経路をノード数Vに対してO(V^2)で求めることが出来ます

1.全てのノードの「暫定最短距離」を「-1」に、「確定フラグ」をOFFにする
2.開始ノード(スタート地点)の「暫定最短距離」を0にする
3.「確定フラグ」がOFFのノードの内、「暫定最短距離」が-1でない最小の値を持つノードの確定フラグをONにする
4.3でONにしたノードから一つの辺を経て到達できる確定フラグがOFFの各ノードに対して
　　A.(経由先の「暫定最短距離」) > (経由元のノードの「暫定最短距離」＋ 辺の重み)　または　経由先の「暫定最短距離」が-1　の場合
　　「経由先の暫定最短距離」＝「経由元のノードの「暫定最短距離」＋ 辺の重み」とし、
　　　経由先の「暫定直前経由ノード」を経由元のノードとする

　　B.(経由先の「暫定最短距離」) < (経由元のノードの「暫定最短距離」＋ 辺の重み)の場合
　　　とくになにも行いません

5.目的のノード(ゴール地点)の確定フラグがONであれば検索を終了し、OFFであれば3に戻ります

これらの操作が終了するとゴール地点のノードの「暫定最短距離」が開始ノードからそのノードへ行くまでの最短距離に相当し
その経由手順は「暫定直前経由ノード」をさかのぼることで得ることが出来ます
連結グラフの場合、終了条件を、全ノードの確定フラグがONであるという条件にすることで、開始ノードから全ノードへの最短距離と経由手順を得ることが出来ます

よくわかんないです †

簡単に説明すると、各ノード間の距離がすべて整数として(簡便のため、距離は1以上とします)

1.スタート地点から距離1で行ける地点を探す。あればそこの地点を確定
2.スタート地点から距離2で行ける地点を探す。
　(この時距離2で行ける地点は「スタート地点、または1で確定した地点から一つの辺を経由してたどり着ける地点」に限定されるはずです)
3.探す距離を増加させていき、目的地が引っかかったらそこで終了

という手順を踏んでいるわけですね。
しかし場合によっては各辺の長さが整数でなかったり、あるいは0だったりしますからそれを「確定フラグ」を用いることで効率的に処理しているわけです

無向グラフに拡張したいです †

無向グラフは例えばA, Bの二つのノードに対してA→Bの辺とB→Aの二つの辺があるグラフとみなせますので
そのまんま同じ手法を使ってください