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

**ダイクストラ法って？ [#l1524da5]
**ダイクストラ法って？ [#m19e33bf]
有向グラフ上の二つのノードを結ぶ最短経路を求める手法です~

**グラフって何？ [#xe08fa0b]
**グラフって何？ [#qbc0f063]

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

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

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


**どういう手順で求めるの？ [#k8aafd1b]
**どういう手順で求めるの？ [#y64e7e7e]
ダイクストラ法では各ノードに2つの情報と1つのフラグを付与する必要があります~

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

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

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

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

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

5.全てのノードについて「更新フラグ」がOFFであれば、計算終了。そうでないなら3に戻る~
　(もし、この時すべてのノードの「更新フラグ」がOFFであるにも関わらず「暫定最短距離」が-1のノードが存在するなら連結グラフではない)~
5.目的のノード(ゴール地点)の確定フラグがONであれば検索を終了し、OFFであれば3に戻ります~

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

注：更新フラグをOFFにするのは、列挙した直後です。4の直後に「3で列挙したノードの「更新フラグ」をOFF」~
という手順だと、4において3で列挙したノードの「暫定最短距離」が更新された場合に問題が発生します~
**よくわかんないです [#p64589a4]

**無向グラフに拡張したいです [#ne72164c]
簡単に説明すると、各ノード間の距離がすべて整数として(簡便のため、距離は1以上とします)~

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

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

**無向グラフに拡張したいです [#md98780b]

無向グラフは例えばA, Bの二つのノードに対してA→Bの辺とB→Aの二つの辺があるグラフとみなせますので~
そのまんま同じ手法を使ってください~
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS