ベルマン-フォード法

概要

ベルマン-フォード法(Bellman-Ford algorithm)は，始点（出発点）の指定された重み付きグラフを入力することで，始点から他の全ての点への最短距離とその経路を出力するアルゴリズムである．負の閉路（一周することができ，そこを一周するための総コストが負となる）が存在する場合は，その閉路を出力する．探索においては，頂点を順番に選び，辺を総当り的に検討してゆく．この作業を頂点の距離の更新がなくなるまで何度も繰り返す．

なお，グラフは始点を除くどの頂点も始点から到達可能であるとする．

アルゴリズム

$\mathrm{dist}(v_i)$を始点から$v_i$への（暫定）距離，$\mathrm{cost}(e_{ij})$を$e_{ij}$のコスト（重み）とする．また，このアルゴリズムでは負の閉路の出力をしない．（すこし手を加えるだけで負の閉路を出力できるようになるので考えてみるとよい．）

入力

頂点の集合$V$
辺の集合$E$（重みの情報も含む）
始点$v_0\in V$

出力

各頂点の始点からの距離
各頂点の直前の頂点

STEP1　グラフの初期化

始点$v_0$の始点からの距離$\mathrm{dist}(v_0)=0$とし，他の頂点の距離は$\infty$（無限大）とする．
また，すべての頂点の直前の点を無し（null）し，すべての頂点の更新フラグを「OFF」とする．

STEP2　距離の更新の反復

（最初は$i=0$からスタートする）
$v_i$からから出ている辺を順番にすべて検討してゆく．$e_{ij}$および$v_j$について，
\begin{equation} \mathrm{dist}(v_i)+\mathrm{cost}(e_{ij})\lt \mathrm{dist}(v_j) \end{equation} なら \begin{equation} \mathrm{dist}(v_j):=\mathrm{dist}(v_i)+\mathrm{cost}(e_{ij}) \end{equation} とし（$:=$はここでは「右辺を左辺に代入する」くらいの意味），$v_j$の直前の点を$v_i$とする．（更新）
また，検討済みの頂点が更新された場合は，その頂点の更新フラグを「ON」にする．

そうでなければ$\mathrm{dist}(v_j)$および$v_j$の直前の頂点は更新しない．


$v_i$からから出ているすべての辺についての検討を終えたら，$i:=i+1$としてSTEP2を反復する．$i=|V|$となったらSTEP3へ進む．

STEP3　終了の判定

更新フラグが「ON」であるような頂点が一つでもあれば，$i:=0$，すべての頂点の更新フラグを「OFF」としてもう一度STEP2の反復をおこなう．

更新フラグがすべて「OFF」であれば探索を終了し，すべての頂点の距離のリストおよびすべての頂点の直前の頂点のリストを出力する．
（ある頂点から直前の頂点を始点まで順にたどってゆくことで最短経路が分かる．）