単一始点最短経路を求めるベルマン・フォード法とは?負の重みにも対応するアルゴリズムを解説

単一始点最短経路問題とベルマン・フォード法

単一始点最短経路問題(single source shortest path problem)を解くための代表的なアルゴリズムがベルマン・フォード法(Bellman-Ford algorithm)です。このアルゴリズムは、重みが正でも負でも構わない任意のグラフにおいて、始点となる頂点(source vertex)から他のすべての頂点への最小距離を求めることができます。

同じく有名な最短経路アルゴリズムであるダイクストラ法との最大の違いは、負の重みを持つ辺の扱いです。ダイクストラ法では負の重みを含むグラフを正しく処理できませんが、ベルマン・フォード法ではこれを容易に扱えます。さらに、グラフ内に負閉路(negative cycle)が存在するかどうかを検出できる点も大きな特徴です。

ベルマン・フォード法はボトムアップ方式で距離を確定させていきます。まず、パスに含まれる辺が1本だけの場合の最短距離を求めます。その後、パス長(辺の数)を1本ずつ増やしながら緩和(relaxation)操作を繰り返し、すべての可能な解を導き出します。頂点数を V とすると、緩和操作を(V−1)回繰り返すことで最短距離が確定します。

入力と出力

入力 ― グラフのコスト行列:

0 6 ∞ 7 ∞
∞ 0 5 8 -4
∞ -2 0 ∞ ∞
∞ ∞ -3 0 9
2 ∞ 7 ∞ 0

出力 ― 始点頂点: 2
Vert: 0 1 2 3 4
Dist: -4 -2 0 3 -6
Pred: 4 2 -1 0 1
このグラフには負閉路は存在しません

アルゴリズム

bellmanFord(dist, pred, source)

入力 ― 距離リスト、先行頂点(predecessor)リスト、および始点頂点。

出力 ― 負閉路が見つかった場合は true を返します。

Begin
   iCount := 1
   maxEdge := n * (n - 1) / 2 //nは頂点数
   グラフのすべての頂点 v について、次を実行する
      dist[v] := ∞
      pred[v] := ϕ
   繰り返し終了
   dist[source] := 0
   eCount := グラフに存在する辺の数
   edgeList という名前の辺リストを作成する
   while iCount < n, do
      for i := 0 to eCount, do
         if dist[edgeList[i].v] > dist[edgeList[i].u] + 辺iのコスト(u,v), then
            dist[edgeList[i].v] := dist[edgeList[i].u] + 辺iのコスト(u,v)
            pred[edgeList[i].v] := edgeList[i].u
      done
      iCount := iCount + 1
   done
   //負閉路の検出
   for すべての辺 i について, do
      if dist[edgeList[i].v] > dist[edgeList[i].u] + 辺iのコスト(u,v), then
         return true
   done
   return false
End

C++による実装例

#include<iostream>
#include<iomanip>
#define V 5
#define INF 999
using namespace std;
//グラフ(有向)のコスト行列、頂点数5
int costMat[V][V] = {
   {0, 6, INF, 7, INF},
   {INF, 0, 5, 8, -4},
   {INF, -2, 0, INF, INF},
   {INF, INF, -3, 0, 9},
   {2, INF, 7, INF, 0}
};
typedef struct{
   int u, v, cost;
}edge;
int isDiagraph(){
   //グラフが有向グラフかどうかを判定
   int i, j;
   for(i = 0; i<V; i++){
      for(j = 0; j<V; j++){
         if(costMat[i][j] != costMat[j][i]){
            return 1;//有向グラフ
         }
      }
   }
   return 0;//無向グラフ
}
int makeEdgeList(edge *eList){
   //グラフの辺から辺リストを作成
   int count = -1;
   if(isDiagraph()){
      for(int i = 0; i<V; i++){
         for(int j = 0; j<V; j++){
            if(costMat[i][j] != 0 && costMat[i][j] != INF){
               count++;//有向グラフの場合の辺の検出
               eList[count].u = i; eList[count].v = j;
               eList[count].cost = costMat[i][j];
            }
         }
      }
   }else{
      for(int i = 0; i<V; i++){
         for(int j = 0; j<i; j++){
            if(costMat[i][j] != INF){
               count++;//無向グラフの場合の辺の検出
               eList[count].u = i; eList[count].v = j;
               eList[count].cost = costMat[i][j];
            }
         }
      }
   }
   return count+1;
}
int bellmanFord(int *dist, int *pred,int src){
   int icount = 1, ecount, max = V*(V-1)/2;
   edge edgeList[max];
   for(int i = 0; i<V; i++){
      dist[i] = INF;//無限大で初期化
      pred[i] = -1;//先行頂点は未検出
   }
   dist[src] = 0;//始点の距離は0
   ecount = makeEdgeList(edgeList); //辺リストの生成
   while(icount < V){ //反復回数は(頂点数-1)
      for(int i = 0; i<ecount; i++){
         if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]){
            //辺を緩和し、先行頂点を設定
            dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v];
            pred[edgeList[i].v] = edgeList[i].u;
         }
      }
      icount++;
   }
   //負閉路の検出テスト
   for(int i = 0; i<ecount; i++){
      if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]){
         return 1;//グラフに負閉路が存在することを示す
      }
   }
   return 0;//負閉路なし
}
void display(int *dist, int *pred){
   cout << "Vert: ";
   for(int i = 0; i<V; i++)
      cout <<setw(3) << i << " ";
   cout << endl;
   cout << "Dist: ";
   for(int i = 0; i<V; i++)
      cout << setw(3) << dist[i] << " ";
   cout << endl;
   cout << "Pred: ";
   for(int i = 0; i<V; i++)
      cout << setw(3) << pred[i] << " ";
   cout << endl;
}
int main(){
   int dist[V], pred[V], source, report;
   source = 2;
   report = bellmanFord(dist, pred, source);
   cout << "Source Vertex: " << source<<endl;
   display(dist, pred);
   if(report)
      cout << "The graph has a negative edge cycle" << endl;
   else
      cout << "The graph has no negative edge cycle" << endl;
}

実行結果

Source Vertex: 2
Vert: 0 1 2 3 4
Dist: -4 -2 0 3 -6
Pred: 4 2 -1 0 1
The graph has no negative edge cycle

計算量と注意点

ベルマン・フォード法の時間計算量は O(V × E)(Vは頂点数、Eは辺の数)、空間計算量は O(V) です。ダイクストラ法よりも処理は遅くなりますが、負の重みを含むグラフに対応でき、負閉路の検出も可能という汎用性の高さが魅力です。

なお、グラフに負閉路が存在する場合、その閉路を通るたびに最短距離は無限に小さくなるため、最短経路自体が定義されません。そこで、(V−1)回の緩和操作を終えた後にもまだ距離の更新が発生するようであれば、「負閉路が存在する」と判定して処理を終了する仕組みになっています。