ベルマンフォード法の概要

• 始点から到達可能な負閉路が存在する場合は、その旨を報告する
• 始点から到達可能な負閉路が存在しない場合は、始点から各点への最短路を求める
  • 負閉路がなければ負辺があっても求められる。

ベルマンフォード法の内容

ベルマンフォード法のアルゴリズムは以下の通り。

頂点の数を $N$ とする。辺 $(u,v)$ 重みを $l(u,v)$ と表すことにする。

始点から頂点 $v$ の距離の各時点での暫定値を $d[v]$ と表すことにする。

• 始点から到達可能な負閉路がない場合は、各辺の緩和を $N-1$ 回行うことで各点への最短路が求まる
  • 最短路は存在すれば高々 $N-1$ 個の辺のみしか経由しないため。
• 始点から到達可能な負閉路が存在する場合は、$N$ 回目の緩和でも更新がされる

  • 証明

  • 図（ここからずっと更新されてしまう）

    

負辺・負閉路の扱い

以下始点から終点には到達可能とする。

• 負辺があっても、負閉路がなければ最短路は存在する
• 負閉路があっても、始点から負閉路に到達できなければ最短路は存在する
  • ベルマンフォード法で解ける（はず）
• 始点から到達可能な負閉路があっても、負閉路から終点に到達できなければ最短路は存在する

  • 例

    

  • 素朴なベルマンフォード法では解けない

  • 負閉路から終点に到達不可能ならば、最短路は存在することになる

    • N回目の緩和で更新された点を求めることで、各負閉路上の点が1つずつ求まる。その点たちからBFSをして終点にたどり着けるか判定すれば良い。
• 始点から到達可能な負閉路であって、その負閉路から終点に到達できる場合は最短路は存在しない
  • 負閉路でコストを十分減らした上で終点に行くことで、終点までのコストをいくらでも小さくできる。

[参考]