dijkstra/

ダイクストラ法

問題まとめ

練習問題

とりあえずやるだけのもの。応用問題を解くための基礎、前提。

• AOJ 単一始点最短経路
  • O(|V^2|) の練習用。
• AOJ 単一始点最短経路2
  • priority queueを用いた O((|E|+|V|)log(|V|)) の練習用。
• AOJ 単一始点最短経路
  • 始点が指定されている以外は↑のものと変わらないはず。

応用問題

少なからず工夫が必要なもの。 ダイクストラが書けるとあとは考察にストレスなく集中できる、というのは多い気がするので、類題にも気負わずに立ち向かいたい。

慣れないうちは、少し考えてもわからなかったら答えを見てもいいと思う。

経路復元が必要な問題を解いてみたい（最短経路木の親、すなわち遷移の1つ前を記憶しておくだけで復元は簡単なはず）。

• ARC061 E.すぬけ君の地下鉄旅行
  • かなり難しい。グラフを工夫して作らないとTLEする。
• ABC143 E.Travel by Car
  • priority queueを使ったダイクストラ法では通らず、2乗オーダーの愚直なダイクストラ法でないと通せない。
• ABC132 E.Hopscotch Addict
  • グラフを工夫してダイクストラ法を行うタイプ。
• yukicoder No.807 umg tours
  • ↑の問題の類題。
• yukicoder No.20 砂漠のオアシス
  • グリッドをグラフとして捉える 部分が最難関かもしれない。ダイクストラの問題ですよと言われると、オアシスの使い方は割と簡単。
• yukicoder No.34 砂漠の行商人
  • 10^8 が想定になっているので、少し厳しいかもしれない。
  • ダイクストラでも解けると思うけど、DPとして見たほうがいい問題かもしれない。
  • 2020-01-04時点で未解決。
• yukicoder No.848 なかよし旅行
  • 星の数の割には難しいと思った。
  • ダイクストラを行った上で、考えられるパターンをできるだけ狭めた上で全探索する。
  • 定数個のSPFAを求めた上で全探索 、というのは典型パターンっぽい。
  • 制約も大きなヒントになる 。
• yukicoder No.160 最短経路のうち辞書順最小
  • 始点から終点経路の出力が求められているので、経路復元ができるようにしなければならない。
  • 本問題で求められている辞書順最小の経路は、ダイクストラで直前のノードを記憶したものから復元することはできない。
    • 解説で特殊な距離を定義すれば行けるとあるが、嘘解法になりえるので非推奨。
  • 蟻本にもある dp[j] = dp[k] + cost[k][j] の条件を利用して求めるのが良い。
    • LCSの復元のようなイメージ。
    • 今回のように選択肢が複数ある場合に最適なものを選ばなければならないケースでは、小回りがきく。
  • ABC146 F.Sugorokuはダイクストラではないが、経路復元パートの考え方が非常に類似しており、重要。
• 第一回PAST J.地ならし
  • 色々と難しいポイントがある気がする。
  • 「ある点で、経由すると左下・右下・右上へ行くのにその点以外に交わらないルートがある」と考えると、その点からの3点への最短経路を考えれば良い。そして、経由点を全探索すれば良い。
  • （正直、想起するのが難しい気がするので、公式解法が知りたい。）
• SoundHound Inc. Programming Contest 2018 Masters Tournament D.Saving Snuuk
  • 自力で解けたのは成長を感じてヨシ。
• ABC035 D.トレジャーハント
  • 有向グラフでも、実は「単一始点・単一終点最短経路」のコストを求めることは容易い。
• ARC011 C.ダブレット
  • ダイクストラ＋経路復元で解ける。
  • 実は単なるBFSでよい。
• ARC056 B.駐車場
  • かなり変わり種だが練習になるかもしれない。
  • 最短距離ではなく、「その頂点に至るまでのパスのうち、最小のノード番号を記憶し、DP値を最大にするように更新していく」というふうにする。
• ABC164 E.Two Currencies
  • 拡張ダイクストラ
• JOI F.ヘビのJOI君 ★★★
• JOI E.森林伐採 ★★
• ABC170 F.Pond Skater
  • 全て拡張ダイクストラ

ダイクストラと見抜くために

• 制約が超重要、ノードの数とエッジの数。
  • エッジの数が少ないなら勝ちやすい。多くてもうまく減らせるのなら適用可能性がある。
  • ノードが不自然に少ないと、制約に応じた全探索にも乗り出せる。

アルゴリズムピックアップ

各ノードの状態を色で考えるのが混乱しなくて良い。

WHITE -> GRAY -> BLACK の順に変化していく。 ただし、始点のみは最初からキューに追加されるため、ループ前に状態を更新する必要がある。

• 初期状態は WHITE
• キューに突っ込んだ時点で GRAY に変化
  • BLACK のものはすでに確定しているのでキューに入れてはいけない。
• キューから取り出すと BLACK に変化
  • 取り出した時点ですでに BLACK であることがあるが、これはキューから取り出されるまでに同じノードが追加されると生じる。
    • そのようなあとから取り出されたものは、ノードのコストが最小ではないので無視して捨ててしまえば良い。

実際の実装手順

ダイクストラはスニペットそのままで使えるケースが少ないので、できるだけゼロから書けるようにする （ただし、priority queueはスニペットで良い）。

以下は忘れたときに見るようだが、可能ならば二度と見たくない。

1. グラフ G を隣接リストで作る

• エッジ構造体 Edge には遷移先のノードID to と重み w が定義されていれば良い。

1. ノード構造体 Vertex とそのpriority queueを定義する

• ノード構造体 Vertex にはノードID id と必要な コスト を定義する必要がある。
• priority queueは、コストに関して昇順となるように適当に Less を定義する必要がある。
  • ここは問題によってまちまちなので注意！
  • とはいえ大抵は int だと思われる。

1. ノードの個数分だけ配列でコスト、色、親それぞれ dp, colors, parents を定義し初期化する。

• dp の型はノード構造体におけるコストの型と一致。
• dp の初期値はいわゆる無限大に当たる値。
• colors の初期値はすべて WHITE 。
• parents に関しては
  • アルゴリズム上は初期値は不要だが、デバッグ等の都合を考えると -1 などがよさそう。

1. キューに始点のノードのみ追加する。

• 追加するノードのコストは 0 とする。
• 始点の状態を変更する dp[s] = 0, colors[s] = GRAY, parents[s] = -1 。
  • 始点の親は当然なし。

1. 以下をキューが空になるまで繰り返す。
2. キューからノード構造体を取り出す。
3. 取り出したノードを BLACK に変更する。 - 冪等性があるので特に条件分岐は考えなくてよい。
4. ノードのコストが dp[cid] より大きい 場合は無視してループを continue する（手順1へ） - 計算量削減のため。
   • 等号を含めて「以上」としては行けないことには注意！等号を入れると一切更新がなされなくなってしまう。 - 5.2の更新前にBLACKかどうかを判定するのも良さそう。
5. ノード構造体から伸びるすべてのエッジについて調べる。
6. 移動先がすでに BLACK の場合は確定しているので continue して次のエッジを調べる。 - 計算量削減のため。
7. そうでない場合かつ、移動先のコスト dp[nid] が dp[cid] + {{エッジのコスト}} よりも大きい場合、小さい方で更新する。
8. 更新したコストでキューに移動先のノード構造体を追加。
9. 移動先の色を GRAY に変更し、親を更新する colors[nid] = GRAY, parents[nid] = cid - 色に関しては冪等性があるので特に条件分岐は考えなくて良い。