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

hamayanhamayan's blog

競技プログラミングにおけるベルマンフォード問題まとめ

ベルマンフォード

  • Bellman-Ford
  • 最短距離を求めるアルゴリズム
  • ダイクストラと違い、負のコストを含む辺があっても正しく動作する
  • 負のサイクルがあると止まらないため、負のサイクル検出ができる
  • 参考
  • 最長距離を求めるようにも書け、その場合は正のサイクル検出ができる(ABC061D)
  • 6Nくらい回せばいいらしい(要出典)