ベルマン・フォード法とは？最短経路を求めるアルゴリズムの基本とC++実装例

ベルマン・フォード法とは

ベルマン・フォード法（Bellman-Ford Algorithm）は、始点（ソース）頂点からグラフ内の他のすべての頂点への最短距離を求めるためのアルゴリズムです。

同じく最短経路問題を解くダイクストラ法との最大の違いは、負の重み（負のコスト）を持つ辺の扱いです。ダイクストラ法では負の重みを含むグラフを正しく処理できませんが、ベルマン・フォード法では負の重みも簡単に扱えます。さらに、グラフ内に負の閉路（ネガティブサイクル）が存在するかどうかを検出できる点も大きな特徴です。

ベルマン・フォード法はボトムアップ（下から上へ）のアプローチで距離を計算します。まず、パスに含まれる辺が1本だけの場合の距離を求め、その後、パス長を段階的に伸ばしながら、すべての可能な経路の解を導き出します。

なお、計算量は O(V×E)（Vは頂点数、Eは辺数）であり、ダイクストラ法より時間はかかるものの、負の重みに対応できる柔軟性が大きな利点となっています。

入力と出力

以下は、5つの頂点を持つ有向グラフのコスト行列を入力とした場合の例です。

入力：
グラフのコスト行列：
0  6  ∞  7  ∞
∞  0  5  8 -4
∞ -2  0  ∞  ∞
∞  ∞ -3  0  9
2  ∞  7  ∞  0

出力：
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

アルゴリズム

bellmanFord(dist, pred, source)

入力： 距離リスト、先行頂点リスト、始点頂点
出力： 負の閉路が見つかった場合は True

Begin
    iCount := 1
    maxEdge := n * (n - 1) / 2    // n は頂点数

    // すべての頂点の距離を無限大で初期化
    for all vertices v of the graph, do
        dist[v] := ∞
        pred[v] := ϕ
    done

    dist[source] := 0
    eCount := グラフに存在する辺の数
    辺リスト edgeList を作成

    // 辺の緩和を（頂点数 - 1）回繰り返す
    while iCount < n, do
        for i := 0 to eCount, do
            if dist[edgeList[i].v] > dist[edgeList[i].u] + cost(u, v), then
                dist[edgeList[i].v] := dist[edgeList[i].u] + cost(u, v)
                pred[edgeList[i].v] := edgeList[i].u
        done
        iCount := iCount + 1
    done

    // 負の閉路の検出
    for all edges i of the graph, do
        if dist[edgeList[i].v] > dist[edgeList[i].u] + cost(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++) {
            // 辺の緩和（relaxation）と先行頂点の設定
            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

実行結果の見方

この例では、始点として頂点2を選択しています。各行の意味は次のとおりです。

• Vert： 各頂点の番号
• Dist： 始点から各頂点までの最短距離
• Pred： 最短経路上における各頂点の直前の頂点（先行頂点）。始点自身は -1 で表されます

最後の行に「The graph has no negative edge cycle」と表示されていることから、このグラフには負の閉路が存在しないことが確認できます。もし負の閉路が存在する場合は、最短距離が確定しないため、その旨が出力されます。