directory
Version:
v0.0.0-...-23e9799
Opens a new window with list of versions in this module.
Published: Jul 15, 2021
License: MIT
Opens a new window with license information.
README
¶
ダイクストラ法
問題まとめ
練習問題
とりあえずやるだけのもの。応用問題を解くための基礎、前提。
応用問題
少なからず工夫が必要なもの。
ダイクストラが書けるとあとは考察にストレスなく集中できる、というのは多い気がするので、類題にも気負わずに立ち向かいたい。
慣れないうちは、少し考えてもわからなかったら答えを見てもいいと思う。
経路復元が必要な問題を解いてみたい(最短経路木の親、すなわち遷移の1つ前を記憶しておくだけで復元は簡単なはず)。
ダイクストラと見抜くために
- 制約が超重要、ノードの数とエッジの数。
- エッジの数が少ないなら勝ちやすい。多くてもうまく減らせるのなら適用可能性がある。
- ノードが不自然に少ないと、制約に応じた全探索にも乗り出せる。
アルゴリズムピックアップ
各ノードの状態を色で考えるのが混乱しなくて良い。
WHITE -> GRAY -> BLACK
の順に変化していく。
ただし、始点のみは最初からキューに追加されるため、ループ前に状態を更新する必要がある。
- 初期状態は
WHITE
- キューに突っ込んだ時点で
GRAY
に変化
BLACK
のものはすでに確定しているのでキューに入れてはいけない。
- キューから取り出すと
BLACK
に変化
- 取り出した時点ですでに
BLACK
であることがあるが、これはキューから取り出されるまでに同じノードが追加されると生じる。
- そのようなあとから取り出されたものは、ノードのコストが最小ではないので無視して捨ててしまえば良い。
実際の実装手順
ダイクストラはスニペットそのままで使えるケースが少ないので、できるだけゼロから書けるようにする
(ただし、priority queueはスニペットで良い)。
以下は忘れたときに見るようだが、可能ならば二度と見たくない。
- グラフ
G
を隣接リストで作る
- エッジ構造体
Edge
には遷移先のノードID to
と重み w
が定義されていれば良い。
- ノード構造体
Vertex
とそのpriority queueを定義する
- ノード構造体
Vertex
にはノードID id
と必要な コスト を定義する必要がある。
- priority queueは、コストに関して昇順となるように適当に
Less
を定義する必要がある。
- ここは問題によってまちまちなので注意!
- とはいえ大抵は
int
だと思われる。
- ノードの個数分だけ配列でコスト、色、親それぞれ
dp, colors, parents
を定義し初期化する。
dp
の型はノード構造体におけるコストの型と一致。
dp
の初期値はいわゆる無限大に当たる値。
colors
の初期値はすべて WHITE
。
parents
に関しては
- アルゴリズム上は初期値は不要だが、デバッグ等の都合を考えると
-1
などがよさそう。
- キューに始点のノードのみ追加する。
- 追加するノードのコストは
0
とする。
- 始点の状態を変更する
dp[s] = 0, colors[s] = GRAY, parents[s] = -1
。
- 以下をキューが空になるまで繰り返す。
- キューからノード構造体を取り出す。
- 取り出したノードを
BLACK
に変更する。
- 冪等性があるので特に条件分岐は考えなくてよい。
- ノードのコストが
dp[cid]
より大きい 場合は無視してループを continue
する(手順1へ)
- 計算量削減のため。
- 等号を含めて「以上」としては行けないことには注意!等号を入れると一切更新がなされなくなってしまう。
- 5.2の更新前にBLACKかどうかを判定するのも良さそう。
- ノード構造体から伸びるすべてのエッジについて調べる。
- 移動先がすでに
BLACK
の場合は確定しているので continue
して次のエッジを調べる。
- 計算量削減のため。
- そうでない場合かつ、移動先のコスト
dp[nid]
が dp[cid] + {{エッジのコスト}}
よりも大きい場合、小さい方で更新する。
- 更新したコストでキューに移動先のノード構造体を追加。
- 移動先の色を
GRAY
に変更し、親を更新する colors[nid] = GRAY, parents[nid] = cid
- 色に関しては冪等性があるので特に条件分岐は考えなくて良い。
Directories
¶
library
|
|
|
|
|
|
|
|
library-2
|
|
|
|
|
|
|
|
|
|
library-3
|
|
|
|
|
|
|
|
|
|
past001-J
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Click to show internal directories.
Click to hide internal directories.