はまやんはまやんはまやん

hamayanhamayan's blog

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

最短経路を求めるには

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

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

  • 問題
  • 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の方が上位互換なのかな?(未検証)