競技プログラミングにおける最短経路問題まとめ [ダイクストラ, ベルマンフォード, ワーシャルフロイド]

最短経路を求めるには

• ダイクストラ【単一始点最短経路】
  • 参考1 参考2
  • 最大値ダイクストラ
    • 応用して各頂点のある値の最大値を求めるダイクストラもある
    • ダイクストラの正負を逆転させただけ
    • 辺が負のコストを持つときに使える
• ベルマンフォード（Bellman-Ford）【単一始点最短経路】
  • ダイクストラと違い、負のコストを含む辺があっても正しく動作する
  • 参考
  • アルゴリズム
    • 1. N-1回ループして最短経路を求める O(NM)
    • 2. N回ループして負のサイクルを見つける O(NM)
  • 最長距離を求めるようにも書け、その場合は正のサイクル検出ができる(ABC061D)
• 幅優先探索 BFS【単一始点最短経路】
  • 辺のコストが1ならばBFSで十分
• ワーシャルフロイド【全頂点間最短経路】
  • 参考1 参考2
  • O(N^3)

問題

• ダイクストラ
  • ARC090 Avoiding Collision 解説
  • JOI 象使い 問題 解説
  • AOJ 認証レベル 解説 （ちょっと変えたダイクストラ）
  • RUPC2018 Day2 Light 解説
  • KOJ No.73 観光計画 解説（最大値ダイクストラ）
  • AC 迷路 解説
  • CF372 Complete The Graph
  • AOJ Gridgedge 解説
  • AOJ スギ (Demon's Cedar) 解説
  • yukicoder No.788 トラックの移動 解説
  • AOJ こたつがめを燃やさないで 解説
  • yukicoder No.807 umg tours 解説
  • [https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g:title=
• ベルマンフォード
  • ABC061 D. Score Attack
  • AOJ Set-constructing Witch (舞台装置の魔女) 解説
  • AOJ The Most Powerful Spell 解説1 解説2
  • 東京工業大学プログラミングコンテスト2015 N. 何かグラフの問題 解説
  • ABC137E Coins Respawn 解説
• BFS
  • いろはちゃんコンテスト Day2 通学路 解説
  • HUPC2019 Day2 E ジャム 解説

• ワーシャルフロイド
  • ABC073 joisino's travel 解説
  • ABC079 Wall 解法
  • CSA70 Min Distances
  • RUPC2017 Day3 AA Graph 解説
  • RUPC2017 Day3 最短距離を伸ばすえびちゃん (Ebi-chan Lengthens Shortest Paths) 解説

発展的話題 KSP: k-th shortest path

• 問題
  • yukicoder No.1069 電柱 / Pole (Hard)
• Yen's Algorithm
  • ↑の問題の想定解法。解説は細かく書いてあるので、見て理解してもいい
  • 計算量はO(KN(M+NlogN)), Kはk-thのk、Nは頂点数、Mは辺数
  • ダイクストラの派生っぽい。たぶんlaycrsさんのツイートで言及している方法と同じだと思う
• Eppstein's Algorithm
  • ↑の問題で使えるかわからないが、こういうのもある。k shortest path routing - Wikipediaを見ると、Yenはlooplessで使えて、Eppsteinはloopyでも使えるとあるので、Eppsteinの方が上位互換なのかな？（未検証）