C++のベルマン・フォード法とは？仕組み・手順・実装例を徹底解説

ベルマン・フォード法（Bellman-Ford Algorithm）は、動的計画法に基づくアルゴリズムの一つで、指定した始点からグラフ内のすべての頂点への最短経路を求めるために使用されます。このアルゴリズムは反復的なアプローチを採用しており、最短経路の候補を繰り返し更新しながら答えを導き出します。重み付きグラフに対して適用できる点が大きな特徴です。

このアルゴリズムは1955年にアルフォンソ・シンベル（Alphonso Shimbel）によって提案されました。その後、1956年と1958年にリチャード・ベルマン（Richard Bellman）とレスター・フォード（Lester Ford）によって改訂され、これが現在のベルマン・フォード法という名称の由来となっています。さらに1957年にはエドワード・F・ムーア（Edward F. Moore）による改訂も行われたため、ベルマン・フォード・ムーア法という名称でも知られています。

このアルゴリズムの最大の強みは、負の重みを持つ辺を扱えることです。ダイクストラ法と比べると計算速度では劣りますが、より多様な種類のグラフに対応できる汎用性の高さが魅力といえます。

アルゴリズムの概要

入力：重み付きグラフと始点
出力：始点からすべての頂点への最短距離
※ 負の閉路が存在する場合、重みを計算できないためその旨が返されます。

処理の手順

ステップ1：初期化ステップ。始点から各頂点への距離を格納する配列 dist[] を作成します。
　　　　　　配列のサイズはグラフの頂点数と同じにします。
ステップ2：頂点間の最短距離を計算します。ステップ3を n-1 回繰り返します（n はグラフの頂点数）。
ステップ3：各辺 i-j について以下の手順を実行します。
　ステップ3.1：dist[v] > dist[u] + weight[uv] が成り立つ場合、dist[v] = dist[u] + weight[uv] に更新します。
ステップ4：負の閉路が存在するかどうかを判定します。ステップ3.1の更新が発生した場合は負の閉路が存在します。

負の閉路（Negative Cycle）とは、通常の辺を辿る経路よりも常に短い経路が存在し続ける状態を指します。このような場合、閉路を一周するたびに総コストが減少し続けるため、最短距離を正確に定義することができません。

具体例

実際にグラフの問題を解きながら、アルゴリズムの動作を詳しく見ていきましょう。

上の図には、グラフのすべての頂点と辺、およびそれぞれに割り当てられた重みが示されています。

それでは、ベルマン・フォード法を使って頂点Aから頂点Eまでの最短距離を求めてみましょう。

まず、始点である頂点Aの距離を0に設定し、その他の頂点の距離はすべて無限大∞に初期化します。

A B C D E
0 ∞ ∞ ∞ ∞

続いて、辺A-B、次にA-Cの重みを順に確認します。

A-Bまでは経路が1つしかありませんが、A-Cには2つの経路が存在するため、どちらが最短になるかを比較しながら更新を行います。

A B  C D E
0 ∞  ∞ ∞ ∞
0 -2 ∞ ∞ ∞   - (A-B) の更新後
0 -2 3 ∞ ∞   - (A-C) の更新後

次に、残りの頂点についても同様に、始点からの最短距離を計算していきます。

A B  C D E
0 ∞  ∞ ∞ ∞
0 -2 ∞ ∞ ∞
0 -2 3 3 10

この結果、ベルマン・フォード法によって求まる最短距離は10で、経路A-B-Eを辿ったときの値となります。また、この計算過程を通じて、グラフ内に負の閉路が存在することも確認できます。

C++での実装例

#include <bits/stdc++.h>
struct Edge {
    int src, dest, weight;
};
struct Graph {
    int V, E;
    struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}
void BellmanFord(struct Graph* graph, int src) {
    int V = graph->V;
    int E = graph->E;
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
        dist[src] = 0;
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
            dist[v] = dist[u] + weight;
        }
    }
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            printf("Graph contains negative weight cycle");
            return;
        }
    }
    printf("Vertex :\t\t\t ");
    for (int i = 0; i < V; ++i)
        printf("%d \t", i);
        printf("\nDistance From Source : ");
    for (int i = 0; i < V; ++i)
        printf("%d \t",dist[i]);
    return;
}
int main() {
    int V = 5;
    int E = 8;
    struct Graph* graph = createGraph(V, E);
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;
    BellmanFord(graph, 0);
    return 0;
}

実行結果

Vertex : 0 1 2 3 4
Distance From Source : 0 -1 2 -2 1

このプログラムでは、5つの頂点と8つの辺を持つグラフを定義し、頂点0を始点としてベルマン・フォード法を実行しています。実行結果を見ると、始点（頂点0）から各頂点への最短距離が正しく出力されていることが分かります。負の重みを持つ辺が含まれるグラフでも、このアルゴリズムなら確実に最短経路を求められる点が、ダイクストラ法との大きな違いです。