ベルマン・フォード法
以下の条件のときに主に用いられる
重みつきグラフ（有向でも無向でも良い）
単一始点最短経路問題
負のコストの辺がある
アルゴリズム
辺の情報をすべてひとつの配列にまとめる
始点のコストは$ 0 に初期化しておき、それ以外の頂点について$ ∞ とする
最短距離が更新されなくなるまで次の操作を繰り返す
辺をひとつづつ走査する
その辺の始点へのコスト+辺のコストが終点へのコストより小さければ、終点へのコストを更新する
負の閉路が存在しない場合は停止する
計算量
任意の頂点への最短経路に同一頂点が2回含まれることはない
通る辺の数は高々$ V−1 本
$ O(VE)
負の閉路
負の閉路がある場合、最小コストが更新され続けるので閉路を無限に回り続けてしまう
通る辺の数は高々$ V−1 本なので辺走査が$ V回行われたら負の閉路があると判断する
負の閉路検出を目的として使われることもある
参考
例題