わかりやすいベルマンフォードアルゴリズムの解説と実装例

単一始点最短経路問題で、辺にマイナスの重みがあるパスがあることがあります。
その際の最短経路を算出する方法としてベルマンフォード法があります。

このベルマンフォード法を図解します。

ベルマンフォードアルゴリズム解説

初期化

頂点をv, 辺をe,頂点uから辺をeを伝って移動する際の重みをw(u,v)とします。
また、開始点から各々の頂点への最短経路を記録した変数をdとします。

まず、dに∞を代入します。
始点(source)には0を代入します。

for each v ∈ V:
  d[v] = ∞
d[s] = 0

頂点から頂点への最短距離を更新する

頂点の数 - 1だけforループを回し、その中で、辺の数分forループを回し、
辺をつなぐ頂点から頂点への最短経路が短くなる場合に最短経路dを更新する処理を行います。
(わかりにくいので、後に図解します)

for i ← 1 to |v| - 1:
  do for each edge (u,v) ∈ E
    do if d[v] > d[u] + w(u,v)
      d[v] = d[u] + w(u,v)

負のサイクルがあるかを検出する

最短経路の確認が終わった後、
最後に負のサイクルがあるかを確認します。

負のサイクルとは、たとえばA → B → C → A
と頂点と辺がつながっているとして、それぞれの重みを{1,2,3,-7}とすると、
A → B → C → Aへの経路は1 + 2 + 3 - 7 = -1
になり、

さらに頂点Aから同じ辺を巡回すると、
A → B → C → A = -1 + 1 + 2 + 3 - 7 = -2

となり、巡回すればするほど、最短経路が短くなるルートのことです。

負のサイクルがある場合は、全ての頂点への最短経路を求められないので、
負のサイクルがあることの報告をします。

最短経路更新プロセスが終わったあと、 再度、最短経路更新できるかで、負のサイクルの検出を行います。

do for each edge (u,v) ∈ E
  do if d[v] > d[u] + w(u,v)
      negative weight cycle

これで、ベルマンフォードのプロセスは終わりです。

図でベルマンフォードの工程を確認する

ベルマンフォードの工程を図解します。

以下のようなグラフがあるとします。
#がついた番号は辺の番号を表します。
今回は#1から最短経路を更新する辺のループプロセスをスタートしますが、
どの辺からループをスタートしても結果は変わりません。
また、頂点の下の数値を最短経路とします。
始点を0にし、それ以外の頂点は∞で初期化します。

ベルマンフォード1回目の試行

辺#1からスタートします。
辺#1はBからEにつながっており、重みは2です。
d[E]は∞なので、∞ > ∞ + 2はfalseとなるので、更新処理は行われません。

辺#2.#3も同様になります。

辺#4はd[A]が0
d[B](∞) > d[A](0) - 1がtrueとなるので、
d[B] = -1
となります。

辺#5も同様で
d[C] = 4

辺#6は更新されず、

#7は
d[C](4) > d[B](-1) + 3がtrueとなり
d[C] = 2になります。

#8は更新されれません。

これで、辺を全てチェックしたので、
一回目の施工が終わります。
このプロセスを頂点 - 1回繰り返すことになります。

1回目の施工を終えると、最短経路は以下のように更新されます。

ベルマンフォード2回目の試行

#1はd[B] = -1なので、d[E] = 1に更新

#2はd[B] = -1なので、d[D] = 1

#3,#4,#5,#6,#7は変わらず

#8は
d[D](0) > d[E](1) - 3がtrueとなるので、
d[D] = -2になります。

2回目の試行の結果は下図ようになります。

ベルマンフォード3回目の試行

3回目以降は、更新処理をしても何も更新されません。
全ての辺の最短経路を更新するプロセスで、
更新がなければ、次の更新時も同じく更新できないので、
ループを抜けて、最短経路を報告します。

負のサイクルのチェック工程

辺の最短経路更新処理が終わったら、負のサイクルチェックするため同じく全辺の最短経路が更新できるか調べる工程に入ります。
今回は、上記の試行の通り更新は行われないので、負のサイクルは存在せず、
始点から各々の頂点への最短経路を求めることができました。

負のサイクルがあるときの処理を確認する

先の試行からわかるように、負のサイクルがあると辺の更新処理を行うたびに、
最短経路が更新されます。

なので、最短経路の更新プロセスが終わった後で、最短経路が更新されれば、
負のサイクルがあることがわかります。

このグラフでは、頂点B → E → D → Bがサイクルになっているので、
このEからDへの重みを-3から-4に変更して負のサイクルに変えて、
考察してみます。

ベルマンフォード負のサイクル1回目の試行

結果は先例の1回目と変わりません

ベルマンフォード負のサイクル2回目の試行

d[D] = -3になります。

ベルマンフォード負のサイクル3回目の試行

d[B] = -2,d[C] = 1に変わります。
これ以降も常に最短経路が短くなりつづけることがわかります。

ベルマンフォードの例題とc++による解答プログラム

AIZU ONLINE JUDGEの例題をもとに、c++の解答を載せます。

#include <vector>
#include <iostream>
using namespace std;
#define MAX 100000
#define INF __INT_MAX__

struct edge{
    // 始点,終点,重み
    int s,t,w;
};

vector edges;
int d[MAX];

void BellmanFord(int startVertex,int vNum,int eNum){
 fill(d,d + MAX,INF);
 d[startVertex] = 0;
 
 // 頂点分回すことで、最後のサイクルは負のサイクルを確認するプロセスになる
 for(int i=0;i < vNum;++i){
  bool update = false;
  for(int j = 0;j < eNum;++j){
   edge e = edges[j];
   if(d[e.s] != INF && d[e.t] > d[e.s] + e.w){
    d[e.t] = d[e.s] + e.w;
    update = true;
    // コード省略のため最短経路を求める工程で負のサイクルプロセス確認工程を行う
    if(i == vNum - 1){
     cout << "NEGATIVE CYCLE" << endl;
     return;
    }
   }
  }
  if(!update)break;
 }

 for(int i = 0;i < vNum;++i){
  if(d[i] == INF){
      cout << "INF"<< endl;
  }
  else cout<< d[i] << endl;
 }
}

int main(){
    int v,e,r;
 cin >> v >> e >> r;
 for(int i = 0;i < e;++i){
  int s,t,w;
  cin >> s >> t >> w;
  edges.push_back({s,t,w});
 }
 BellmanFord(r,v,e);
}