Skip to content

最短路問題

Jump to bottom
Yuta Kasai edited this page Jun 29, 2018 · 14 revisions

H1 最短路問題

  • ダイクストラ
  • ワーシャルフロイド
  • ベルマンフォード(差分制約除く)
  • (SPFA)
  • 最短路DAG
  • 最短路の性質
  • 巡回セールスマン問題/中国人郵便配達問題(bitDP)

AOJは実装メインで、atcoderは考えるのがメインかも…

H2 計算量

  • ダイクストラ 実装による O(V^2)からO((E+V)logV)が有名(二分ヒープを使用すると操作が全部logになる)
    • E=V^2で改悪となることが知られているが、ならし計算量が削除O(logN),他O(1)のフィボナッチヒープを使用すればO(E+VlogV)となりまあ改悪というほどではなくなる(嘘をついている人が多い)
    • yosupoさんのスライド
  • ベルマンフォード O(EV)
    • V回更新されるときは発散している
    • ダイクストラは負の辺はダメだけどこっちは更新方法からできる
  • ワーシャルフロイド O(V^3)
    • 上記はS-T最短路だが、全点間の最短路が求められる(うれしい)
    • 証明したことがないと解けない問題がSRMdiv2hardで出た
    • 1行で書けるので便利
  • SPFA O(EV)
    • ダイクストラがあるのでお役御免感…
  • bitDP O(N^2*2^N)
    • 巡回セールスマン問題とか順序関係があるやつでO(N!)を改善するやつ

H2 よくあるもの

  1. 経由地点の指定
  2. 経路復元
    • 最短路を更新したときに遷移を保存して、ゴールからたどれば良い
    • 辞書順最小は工夫する(ゴールを始点にすれば辞書順最小が保証される) submission
  3. 状態の区別
    • 拡張ダイクストラという人が多い、AOJICPCに頻出
    • 慣れれば書くだけ(前いた場所、パラメータ等)
    • 最短路上で区別しないといけないものをわけただけ…
  4. 辺を反転
    • したくなる時がある
    • 補グラフもしたくなる時がある
  5. 最短路DAG&性質
    • 全然しらないけどなんとかなっている
    • 最短路のpathの総数はDPっぽくできる

H3 特殊な使い方

  • 負閉路判定はベルマンフォード、ワーシャルフロイドでもできる
    • 計算量は圧倒的にBFSが良いけどサクッとかける
  • 双方向ダイクストラ
  • 最短経路はLPともみれるので、差分制約を最短路に落とし込むことがある

H4 問題例

AC AOJ 2249 Road Construction (最短路の性質)

ダイクストラ
AC AOJ GRL1 A (verified)
AC AOJ 0212 高速バス (拡張)
AC AOJ 1156 ちょろちょろロボット (前の遷移)
AC AOJ 2151 勇敢なお姫様またも現る (拡張)
AC AOJ 0596 タクシー (拡張)
AC AOJ 1138 駅馬車旅行 (bitDP)
AC AOJ 1150 崖上り (拡張)
AC AOJ 2021 お姫様の危機 (拡張)
AC AOJ 0155 Spider Jin (経路復元)
AC AOJ 0562 JOI国の買い物事情 (最短路の性質?)
AC AOJ 1162 離散的速度 (拡張 前の遷移も)
TRY AOJ 0601 フクロモモンガ ()
AC AOJ 1183 鎖中経路 (最短路+幾何)
AC AOJ 2585 一日乗車券 (拡張+bit部分集合)
TRY HOJ 0012 Jakarta Skyscrapers (まだみてない)
AC AOJ 2447 A Two Floors Dungeon ()
AC ABC 051 D Candidates of No Shortest Paths (最短路の性質?)
AC ARC 061 E すぬけ君の地下鉄旅行 (二部グラフ + 実装 + UnionFind)
AC ARC 064 E Cosmic Rays (最短路)
AC yukicoder 160 最短経路のうち辞書順最小 (辞書順最小の経路復元)
AC Uva 12680 Shopping Malls (最短路+経路復元)
AC AOJ 0558 チーズ (経由地点)
AC AOJ 1311 TestCase Tweaking (コスト変更)

ベルマンフォード
差分制約はLPに書いた
AC ABC 061 D Score Attack (ダイクストラはダメな例)

ワーシャルフロイド
AC AOJ verify用 ()
AC AOJ 0117 大工の褒美 ()
AC AOJ 0200 - 高校生一人旅 青春の片道切符編 ()
AC AOJ 0189 - 便利なのはどこ？ ()
AC AOJ 0526 - 船旅 ()
AC AOJ 2005 - Water Pipe Construction ()
AC AOJ 2200 Mr. Rito Post Office ()
AC AOJ 1182 - 鉄道乗り継ぎ ()
AC ABC 079 D Wall ()
AC AOJ 2774 成長する点 (最短路更新の性質?)
FAV SRM 710 div2 hard MinMaxMax (超良問)
AC AOJ 2827 凸多角形柱工業都市 (+幾何)

bitDP
AC AOJ 巡回セールスマン問題 ()
AC AOJ 中国人郵便配達問題 ()
AC AOJ 2672 郵便局員を救え (bitDP)

BFS

AC AOJ 1290 (+さいころ)
AC AOJ 2451 (+さいころ)
AC ()
AC ()

Clone this wiki locally