C言語で実装するベルマン–フォード法を解説：負の辺にも対応する最短経路アルゴリズム

この記事では、C言語を使ったベルマン–フォード法の実装例について解説します。

負の辺を含むグラフでも最短経路を求められる点に注目し、実際のコード例を交えながら処理の流れや注意点を分かりやすく説明します。

アルゴリズムの基本概要

ベルマン–フォード法は、単一始点から各頂点への最短経路を求めるアルゴリズムです。

グラフ内に負の辺が含まれる場合でも適用できるため、幅広い用途に対応できます。

計算は各辺の緩和操作を繰り返し実施することで行われ、全体の計算量は辺の数と頂点の数に依存します。

特に、グラフに負のサイクルが存在する場合は、アルゴリズムの特別な動作が必要となる点に注意してください。

ベルマン–フォード法の特徴

ベルマン–フォード法は、以下の点で特徴的です。

• 単一始点から全頂点への最短経路を求められます。
• 負の辺を含むグラフにも対応できるため、Dijkstraのアルゴリズムが使えない場合でも利用可能です。
• 緩和処理を頂点数 minus 1 回繰り返すため、計算量が$O(VE)$となります。
• 全頂点の更新後にもう一度緩和処理を行い、負のサイクルが存在するかどうかをチェックできます。

負の辺と負のサイクルへの対応

ベルマン–フォード法は、負の重みを持つ辺を正しく処理できる設計になっています。

負の辺そのものは計算に影響を与えませんが、負のサイクルが存在する場合、最短経路が定義できなくなるため、その検出が重要です。

負のサイクルの検出では、すべての辺に対して一度以上の緩和が可能かどうかを判定します。

もし緩和が可能な場合は、グラフ内に負のサイクルがあると判断され、ユーザーに警告を出す実装とするのが一般的です。

C言語による実装手法

C言語でのベルマン–フォード法の実装では、プログラム全体を明確に分割し、各処理を順次実施する設計とすることが大切です。

以下、具体的な実装手法について解説します。

プログラム構成の概要

プログラムは主に以下のパートに分かれます。

データ構造の定義と初期化

まず、頂点と辺の情報を管理するために構造体を定義します。

たとえば、辺を表す構造体としてEdgeが利用され、各辺は始点、終点、重みの情報を保持します。

また、各頂点までの最短距離を格納する配列も用意し、全体の初期化は定数$\mathrm{\infty }$で行います。

初期状態では、始点のみを0に設定し、他は$\mathrm{\infty }$の値にします。

入力処理と辺情報の管理

グラフの頂点数や辺の数などの入力情報は、ユーザーからの入力またはファイルから読み込みます。

各辺の情報は動的に確保した配列または固定サイズの配列に格納し、アルゴリズム実行前に正しく初期化されるよう管理します。

入力チェックも適切に実装することで、不正なデータが与えられた場合の対処も行います。

緩和処理の実装

緩和処理は、各辺を検証しながら最短経路情報を更新する処理です。

ベルマン–フォード法のコアとなる部分であり、効率的な実装が求められます。

各辺の緩和処理の詳細

各辺の緩和処理では、辺の始点から終点への経路が既存の最短経路よりも短い場合に更新を行います。

具体的には、辺Edge eを用いて、条件

$$distance[e.from]+e.weight<distance[e.to]$$

が成立する場合、distance[e.to]の値を更新します。

C言語では、配列のインデックスや構造体のメンバに直接アクセスすることで、効率的に処理を進める実装とします。

繰り返し処理の設計

緩和処理は、頂点数$V$に対して$V–1$回繰り返します。

なお、各回のループごとに全ての辺の緩和を試みるため、ネストされたループ構造となります。

また、一度の反復で更新がなかった場合は、アルゴリズムを打ち切る最適化も実装することで、不要な計算を省くことができます。

負のサイクル検出

負のサイクルが存在すると、最短経路が無限に小さな値に更新される可能性があります。

そのため、アルゴリズムの最後に追加の検査処理が必要です。

検出手法とチェック条件

全ての緩和処理後に、辺の緩和がさらに可能かどうかをチェックします。

具体的には、再度各辺に対して以下の条件を確認します。

$$distance[e.from]+e.weight<distance[e.to]$$

もしこの条件が成立する場合、グラフ内に負のサイクルが存在すると判断します。

このチェックを行うことで、ユーザーへ負のサイクルの存在を知らせる仕組みを実装し、誤った結果を防ぐ対策とします。

コード解説と動作確認

以下では、ベルマン–フォード法のC言語によるサンプルコードを具体的に紹介し、各部分の動作を確認できる手順について説明します。

サンプルコードの紹介

以下にサンプルコードを示します。

コード内のコメントは日本語で記述し、関数名や変数名は英語表記としています。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF INT_MAX  // 定数値 INF の定義
// Edge 構造体: 各辺の情報を保持
typedef struct {
    int from;   // 辺の始点
    int to;     // 辺の終点
    int weight; // 辺の重み
} Edge;
// ベルマン–フォード法の実装関数
int bellmanFord(int vertexCount, int edgeCount, Edge edges[], int start, int distance[]) {
    // 全頂点の初期化。始点は 0、その他は INF に設定
    for (int i = 0; i < vertexCount; i++) {
        distance[i] = INF;
    }
    distance[start] = 0;
    // 頂点数 - 1 回の緩和処理を行う
    for (int i = 0; i < vertexCount - 1; i++) {
        for (int j = 0; j < edgeCount; j++) {
            int u = edges[j].from;
            int v = edges[j].to;
            int w = edges[j].weight;
            if (distance[u] != INF && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
            }
        }
    }
    // 追加ループによる負のサイクル検出
    for (int j = 0; j < edgeCount; j++) {
        int u = edges[j].from;
        int v = edges[j].to;
        int w = edges[j].weight;
        if (distance[u] != INF && distance[u] + w < distance[v]) {
            return -1;  // 負のサイクルが検出された場合は -1 を返す
        }
    }
    return 0;  // 正常終了の場合は 0 を返す
}
int main() {
    // サンプルグラフの定義: 例として 5 頂点、8 辺のグラフ
    int vertexCount = 5;
    int edgeCount = 8;
    Edge edges[8] = {
        {0, 1, 6},
        {0, 2, 7},
        {1, 2, 8},
        {1, 3, 5},
        {1, 4, -4},
        {2, 3, -3},
        {2, 4, 9},
        {3, 1, -2}
    };
    int start = 0;  // 始点の設定
    int distance[vertexCount];  // 各頂点への最短距離を格納する配列
    int result = bellmanFord(vertexCount, edgeCount, edges, start, distance);
    // 負のサイクルが検出された場合の処理
    if (result == -1) {
        printf("負のサイクルが検出されました。\n");
        return 1;
    }
    // 各頂点への最短距離の表示
    printf("頂点 %d からの最短距離:\n", start);
    for (int i = 0; i < vertexCount; i++) {
        if (distance[i] == INF) {
            printf("頂点 %d: 到達不能\n", i);
        } else {
            printf("頂点 %d: %d\n", i, distance[i]);
        }
    }
    return 0;
}

頂点 0 からの最短距離:
頂点 0: 0
頂点 1: 2
頂点 2: 7
頂点 3: 4
頂点 4: -2

コンパイルおよび実行手順

以下の手順に沿って、サンプルコードをコンパイルおよび実行してください。

1. ファイル名をたとえば bellman_ford.c として保存します。
2. ターミナルまたはコマンドプロンプトを開き、次のコマンドを入力してコンパイルします。

gcc -o bellman_ford bellman_ford.c

3. コンパイルに成功したら、次のコマンドで実行します。

./bellman_ford

実行結果は上記のコードブロックに示した通りになります。

まとめ

この記事では、ベルマン–フォード法の基本や特徴、特に負の辺や負のサイクルへの対応方法について解説しています。

C言語を用いた実装例を通して、プログラムのデータ構造の定義、入力処理、各辺の緩和処理、繰り返し処理の設計、そして負のサイクル検出の仕組みについて具体的に示しました。

これにより、実際の動作確認方法やコードの構成が理解しやすくなり、実用的なプログラミングの参考となる内容を提供しています。