ベルマン-フォード法

単一始点最短経路問題(SSSP)を解くためのアルゴリズムのひとつ。
ダイクストラ法より計算量は大きいが負の辺が含まれていても利用ができる。また、負の閉路が存在する場合検出することも可能。

実装

いずれかの頂点で最短距離が更新されなくなるか、$|V|$回目の更新が終わるまで繰り返す。
最短距離を更新する処理はすべての辺に対して、辺の終点の$v$の最短距離より辺の始点の$u$の最短距離+辺の重みのほうが小さい場合、最短距離を更新する。

$$d[v] = min(d[u] + 辺eの重み)$$

１回の更新で少なくとも１つの頂点の最短距離が決まるため、始点となる頂点を除いた$|V|-1$回の更新で最短距離が求まる。
グラフ上に負の閉路が存在する場合、最短距離の更新が必ず発生するため、$|V|-1$回の更新で終わらない。よって、$|V|$回更新された場合、負の閉路が存在することがわかる。

すべての頂点の最短経路がわかるまですべての辺の走査を$|V|-1$回の更新を繰り返すため、計算量は$O(|V| \times |E|)$となる。

距離の最大化

最短距離ではなく最大化したい場合、グラフの辺に$-1$をかけることで最大化を計算できる。
これは負の辺が存在しても計算できるために利用できる方法。ダイクストラではこの方法は適用できない。

問題

参考