アルゴリズムの概要

ベルマンフォード法は、グラフ理論における単一始点最短経路問題を解決するためのアルゴリズムです。ダイクストラ法と比較して計算量は大きくなりますが、辺の重みが負の値を含む場合でも正しく動作するという特徴があります。また、アルゴリズムの過程で負の閉路（負の重みを持つサイクル）が存在するかどうかも検出可能です。

動作原理

このアルゴリズムの核心は「緩和（relaxation）」操作にあります。頂点数を \(V\) とした場合、すべての辺に対して \(V-1\) 回繰り返し緩和処理を行うことで、始点から各頂点までの最短距離を確定させます。もし \(V\) 回目以降も更新が発生する場合は、そのグラフに負の閉路が含まれていることを意味します。

具体的な手順は以下の通りです。

1. 始点からの距離を 0、それ以外の頂点からの距離を無限大で初期化します。
2. すべての辺について、始点側の距離＋辺の重みが、終点側の現在の距離より小さい場合、終点側の距離を更新します。
3. この更新処理を頂点数 minus 1 回繰り返します。
4. 更新が行われなくなった時点で処理を終了します。

C++ による実装例

以下は、辺のリストを用いてベルマンフォード法を実装した C++ のコードです。変数名や構造体定義を独自に変更し、ロジックの可読性を高めています。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 辺の情報を保持する構造体
struct Link {
    int src;
    int dest;
    int weight;
};

const int INF_VALUE = 0x3f3f3f3f;
const int MAX_NODES = 1000;
const int MAX_EDGES = 1000;

int main() {
    int node_count, edge_count;
    cin >> node_count >> edge_count;

    vector<Link> graph;
    for (int i = 0; i < edge_count; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph.push_back({u, v, w});
    }

    // 距離の初期化
    vector<int> min_cost(node_count, INF_VALUE);
    int start_node = 0;
    min_cost[start_node] = 0;

    // 緩和処理の繰り返し
    for (int i = 0; i < node_count - 1; ++i) {
        bool has_changed = false;
        for (const auto& e : graph) {
            if (min_cost[e.src] != INF_VALUE && min_cost[e.dest] > min_cost[e.src] + e.weight) {
                min_cost[e.dest] = min_cost[e.src] + e.weight;
                has_changed = true;
            }
        }
        // 更新がなければ早期終了
        if (!has_changed) break;
    }

    // 結果の出力
    for (int i = 0; i < node_count; ++i) {
        cout << min_cost[i] << " ";
    }
    cout << endl;

    return 0;
}

MATLAB による実装例

MATLAB を使用した場合、隣接行列または辺リストを用いて同様の処理が可能です。ここでは、圧縮された辺のリストから行列を生成し、最短距離と親ノードを記録する実装を示します。

% 辺データの定義 (始点，終点，重み)
edge_data = [
    1 2 6;
    1 3 5;
    1 4 8;
    2 5 9;
    2 3 -2;
    3 5 -3;
    4 3 -3;
    5 1 2;
    3 4 7
];

% 頂点数の算出
node_count = max(max(edge_data(:, 1:2)));

% 隣接行列の生成
adj_matrix = inf(node_count, node_count);
for i = 1:size(edge_data, 1)
    u = edge_data(i, 1);
    v = edge_data(i, 2);
    w = edge_data(i, 3);
    adj_matrix(u, v) = w;
end

% 距離ベクトルと親ノードの初期化
distances = inf(1, node_count);
distances(1) = 0;
parents = zeros(1, node_count);
parents(1) = 1;

prev_parents = ones(1, node_count);

% 収束するまで繰り返し
while sum(prev_parents == parents) ~= node_count
    prev_parents = parents;
    for i = 1:node_count
        if prev_parents(i) ~= 0
            for j = 1:node_count
                if adj_matrix(i, j) ~= inf
                    if distances(j) > distances(i) + adj_matrix(i, j)
                        distances(j) = distances(i) + adj_matrix(i, j);
                        parents(j) = i;
                    end
                end
            end
        end
    end
end

% 計算結果の表示
disp('最短距離:');
disp(distances);
disp('親ノード:');
disp(parents);

このスクリプトでは、`distances` 配列に始点から各ノードへの最小コストが格納され、`parents` 配列には経路復元用の前駆ノードが記録されます。負の閉路が存在しない場合、この繰り返し処理によって最適解が得られます。