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

hamayanhamayan's blog

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

最短経路を求めるには

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