ベルマン-フォード法 - 情報科学と人工知能のノート

最短経路問題を解くアルゴリズム．ベルマンとフォードが共著の論文で一つのアルゴリズムを提案したわけじゃないようなのですが、なんでベルマン-フォード法って呼ぶのでしょうね？*1

定義

入力：グラフ $G=(V,E)$ 、コスト関数 $c:E\rightarrow\mathbb{Q}_{\geq 0}$ 、始点 $s\in{V}$ 、終点 $t\in{V}$ ．
解：始点から終点への経路．すなわち、次を満たす頂点と辺の列（ただし）．
- $v_0=s$ 、
- $v_k=t$ 、
- 任意の $i\in[1,\cdots,k]$ について $e_i=\{v_{i-1},v_{i}\}$ ．
解のコスト：経路に含まれる各辺のコストの和．
出力：グラフにコストが負の閉路が含まれる場合はその旨を報告して異常終了．そうでなければコスト最小の解を返す．

グラフにコストが負の閉路が含まれる場合、そこをぐるぐる回ることによって経路のコストを無限に減らせるため、最小コストの経路が存在できなくなるわけです．しかし、ベルマン-フォード法は負の閉路の検知ができるため、上記のような出力になります．

直観的なアイディア

まず前提として、始点ではない任意の頂点 $v$ について、始点から $v$ への最短経路は（もし存在するならば）、始点から別の頂点 $u$ への最短経路に $v$ を加えた形に必ずなっています．何故ならば、始点から $u$ への最短ではない経路に $v$ を付け加えた形の経路は、 $u$ への経路の部分を最短経路に置き換えることによってコストを削減することができるからです．

よって、終点に単一の辺で接続されている頂点への最短経路に終点を加えたもののうち、コストの最も小さなものを選べばそれが始点から終点への最短経路になっているわけですが、すると今度は始点から別の頂点への最短経路問題を解かなければなりません．

ベルマン-フォード法では、始点からの最短経路に含まれる辺の本数が等しい頂点ごとに、まとめて最短経路を定めていきます．

まず、グラフがコストが負の閉路を含まない場合、始点から始点への最短経路はコストも辺の数も 0 の空列です．そこで、始点に 0、それ以外の頂点に無限大のマークをメモしておきます．このメモは「0 本以下の辺だけからなる経路を考えたとき、始点から始点への最短経路のコストは 0、始点から他の頂点への最短経路のコストは無限大（経路が無い）」という意味です．

後は、以下の処理をメモの値が変更されなくなるまで繰り返すだけです．全ての頂点 $v$ について、上記の終点のように、 $v$ と単一の辺で接続されている頂点への最短経路に $v$ を加えた経路の最小のコストを計算し、メモする．例えば繰り返しが $i$ 回目のとき、この処理は「始点から各頂点への $i-1$ 本以下の辺だけからなる最短経路を用いて、始点から各頂点への $i$ 本以下の辺だけからなる最短経路を計算する」ことに対応します． $i-1$ 本以下の辺だけからなる最短経路が真の最短経路であるような頂点についてはメモの値は変化しません．

最後に問題となるのは、繰り返しを何回繰り返せばよいかです．グラフの頂点の個数を $n$ とおきます．グラフに負のコストの閉路が存在しない場合、始点から任意の頂点への最短経路は $n-1$ 個の辺しか含みません．なぜならば、頂点が $n$ 個しかないので、 $n$ 個以上の辺からなる経路は必ず閉路（ループ）を含んでいるからです．そして、グラフが負のコストを持たないという前提なので、この閉路の部分のコストは非負、すなわちこの閉路を経路から取り除けば経路のコストを下げることができます．
逆に言うと、更新処理を $n$ 回繰り返してもまだメモの値が変化するようなら、グラフは負のコストの閉路を持っているということになります．

擬似コード

以上をまとめると、ほとんど上記の説明そのままですが、擬似コードは以下のようになります．

$C_1[v] \leftarrow \infty, \forall v \in V$ ; // 始点からのコストを保存する配列
$C_2[v] \leftarrow \infty, \forall v \in V$ ; // $C_1$ のダブルバッファリング用の配列
$C_1[s] \leftarrow 0$ ;
$i \leftarrow 0$ ;
${\rm while} C_1 \neq C_2$
　　 ${\rm if} i = n$
　　　　負の閉路を検出したので報告して異常終了;
　　 $i++$ ;
　　 $C_2 \leftarrow C_1$ ;
　　 ${\rm for} $u, v$ \in E$
　　　　 ${\rm if} C_1[v] > C_2[u] + c(\{u,v\})$
　　　　　　 $C_1[v] \leftarrow C_2[u] + c(\{u,v\})$ ;
${\rm endwhile}$
ダイクストラ法のように始点から終点への経路を出力して終了;