ベルマンフォード法

ベルマンフォード(Bellman-Ford)法は単一始点最短経路問題のアルゴリズムの一種です。

ダイクストラ法との違いは、負の辺の取り扱いに対応しており、負の閉路の検出が可能である点です。
ただし、計算量はダイクストラ法の方が少ないため、負辺が存在しない場合は基本的にダイクストラ法を使用したほうが良いです。

アルゴリズム

まず、閉路のない場合を考え、頂点数を|V|, 辺の数を|E|とします。
上のグラフの場合、|V| = 6、|E| = 8です。

始点から終点まで到達できる場合、最短経路の移動回数は高々|V-1|回です。
なぜなら今考えているグラフには負の閉路は存在しない為、1度訪れたノードに戻ることは無いからです。
(背理法で証明可能?)

さて、|V|-1回の更新で十分であることは分かりました。
あとは各頂点からについてどの頂点から来た場合が最小コストであるかを知る必要があります。。
そこで、「全ての辺について最小コストを更新をする」動作を|V-1|回繰り返せばどの頂点から来れば最小コストとなるのかが求まります。

↓「全ての辺について最小コストを更新をする」に該当するコード

実際その動作を行えば良く、オーダーはO(|V|*|E|)となります。

閉路の検出

解法

「上記アルゴリズムを実行後、もう|V|回繰り返して終点のコストが更新されたら負の閉路が存在する」という解法を思い付きますが、実はこれでは不十分です。

反例

以下の例の場合を考えてみましょう。

(|V|-1)*|E|回の更新で、ゴールへ向かう最小コストは-10000000000であると求められます。
-1の負のループが存在し、実際の最小コストは-INFとなるわけですが、これ検出するには2*|V|*|E|回の更新では不十分であることがわかります。
(-10000000003回の更新を繰り返さないといけません)

正しい解法

「|V|-1回更新更新を行った後でも、始点から終点への経路上にある頂点の最小コストが更新可能である」場合に負の閉路が存在します。

「始点から終点への経路上にある頂点」とは、以下の性質を満たします。

  1. 始点からその頂点に到達可能
  2. その頂点から終点に到達可能
    ( = 逆辺のグラフで、終点からその頂点に向かうことが出来る)

1, 2はそれぞれDFSまたはqueueで求めることが可能です。

実装

 

関連問題