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

hamayanhamayan's blog

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

最短経路を求めるには

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