ベルマンフォード法完全解説 - 負辺対応の最短経路アルゴリズム

負の重みを持つ辺がある場合でも最短経路を見つけられるベルマンフォード法について、実装から最適化まで実践的に解説します。

こんな課題でお困りではありませんか？

「ダイクストラ法で最短経路を実装したけれど、負の重みがある場合に正しく動作しない」 「グラフ理論のアルゴリズムを業務で使いたいが、どの手法を選べばいいかわからない」 「最短経路アルゴリズムの理論は分かるが、実際のコードで詰まってしまう」

こうした悩みを抱える開発者の方は多いのではないでしょうか。特に、物流システムやネットワーク最適化、ゲーム開発などでは、負の重みを持つ辺を含むグラフの最短経路問題に直面することがあります。

今回は、こうした課題を解決できるベルマンフォード法について、20年以上Web開発に携わってきた経験をもとに詳しく解説していきます。

なぜダイクストラ法では対応できないのか

最短経路アルゴリズムとして有名なダイクストラ法には重要な制限があります。それは負の重みを持つ辺があるグラフでは正しく動作しないということです。

あるクライアントでは、配送コストの最適化システムを構築する際、割引やキャッシュバックを「負のコスト」として表現しようとした際に、この問題に直面しました。ダイクストラ法では、一度確定した頂点の最短距離は更新されないため、後から見つかる負の辺による改善を見逃してしまうのです。

ベルマンフォード法の仕組みと実装

基本アルゴリズムの概要

ベルマンフォード法は、単一始点最短経路問題を解くアルゴリズムで、以下の特徴があります：

• 負の重みを持つ辺に対応
• 負閉路の検出が可能
• 時間計算量は O(VE)（V: 頂点数、E: 辺数）

具体的な実装手順

実際のクライアント案件で使用したコードをベースに、段階的に解説していきます。

class BellmanFord {
    private $vertices;
    private $edges;
    
    public function __construct($vertices) {
        $this->vertices = $vertices;
        $this->edges = [];
    }
    
    // 辺の追加
    public function addEdge($source, $destination, $weight) {
        $this->edges[] = [
            'source' => $source,
            'destination' => $destination,
            'weight' => $weight
        ];
    }
    
    // ベルマンフォード法の実行
    public function findShortestPath($start) {
        // 距離の初期化
        $distance = [];
        for ($i = 0; $i < $this->vertices; $i++) {
            $distance[$i] = PHP_INT_MAX;
        }
        $distance[$start] = 0;
        
        // (頂点数 - 1) 回緩和処理を繰り返す
        for ($i = 0; $i < $this->vertices - 1; $i++) {
            foreach ($this->edges as $edge) {
                $u = $edge['source'];
                $v = $edge['destination'];
                $w = $edge['weight'];
                
                if ($distance[$u] != PHP_INT_MAX && 
                    $distance[$u] + $w < $distance[$v]) {
                    $distance[$v] = $distance[$u] + $w;
                }
            }
        }
        
        // 負閉路のチェック
        foreach ($this->edges as $edge) {
            $u = $edge['source'];
            $v = $edge['destination'];
            $w = $edge['weight'];
            
            if ($distance[$u] != PHP_INT_MAX && 
                $distance[$u] + $w < $distance[$v]) {
                throw new Exception('負閉路が検出されました');
            }
        }
        
        return $distance;
    }
}

class BellmanFord {
    constructor(vertices) {
        this.vertices = vertices;
        this.edges = [];
    }
    
    addEdge(source, destination, weight) {
        this.edges.push({ source, destination, weight });
    }
    
    findShortestPath(start) {
        // 距離の初期化
        const distance = new Array(this.vertices).fill(Infinity);
        distance[start] = 0;
        
        // (頂点数 - 1) 回緩和処理
        for (let i = 0; i < this.vertices - 1; i++) {
            for (const edge of this.edges) {
                const { source: u, destination: v, weight: w } = edge;
                
                if (distance[u] !== Infinity && 
                    distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                }
            }
        }
        
        // 負閉路チェック
        for (const edge of this.edges) {
            const { source: u, destination: v, weight: w } = edge;
            
            if (distance[u] !== Infinity && 
                distance[u] + w < distance[v]) {
                throw new Error('負閉路が検出されました');
            }
        }
        
        return distance;
    }
}

使用例

実際の業務で使用した例を紹介します。配送ルート最適化システムで、キャッシュバック（負の重み）を考慮した最適ルートを求める場合：

// グラフの作成（5つの配送拠点）
$bf = new BellmanFord(5);

// 通常のコスト
$bf->addEdge(0, 1, 10);  // 拠点0→1: コスト10
$bf->addEdge(0, 2, 5);   // 拠点0→2: コスト5
$bf->addEdge(1, 3, 1);   // 拠点1→3: コスト1
$bf->addEdge(2, 1, 3);   // 拠点2→1: コスト3
$bf->addEdge(2, 3, 9);   // 拠点2→3: コスト9
$bf->addEdge(3, 4, 2);   // 拠点3→4: コスト2

// キャッシュバック（負のコスト）
$bf->addEdge(1, 2, -7);  // 拠点1→2: キャッシュバック7

try {
    $distances = $bf->findShortestPath(0);
    foreach ($distances as $vertex => $distance) {
        echo "拠点0から拠点{$vertex}への最小コスト: {$distance}\n";
    }
} catch (Exception $e) {
    echo "エラー: " . $e->getMessage() . "\n";
}

よくある失敗パターンと対処法

1. 初期化の誤り

失敗例: 距離配列を0で初期化してしまう

// 間違った初期化
$distance = array_fill(0, $vertices, 0);

正しい方法: 開始点以外は無限大で初期化

// 正しい初期化
for ($i = 0; $i < $this->vertices; $i++) {
    $distance[$i] = ($i === $start) ? 0 : PHP_INT_MAX;
}

2. 負閉路検出の忘れ

クライアントプロジェクトでは、負閉路の存在を見逃してシステムが無限ループに陥るケースがありました。必ず負閉路検出を実装しましょう。

3. 大規模グラフでの性能問題

ベルマンフォード法は O(VE) の時間計算量を持つため、大規模なグラフでは処理時間が問題になることがあります。

対処法:

• **SPFA（Shortest Path Faster Algorithm）**の採用
• グラフの事前分析による最適化
• 並列処理の活用

4. メモリ効率の改善

大規模グラフでは、隣接リストによる表現を使用することでメモリ使用量を削減できます：

class OptimizedBellmanFord {
    private $graph;
    
    public function __construct() {
        $this->graph = [];
    }
    
    public function addEdge($from, $to, $weight) {
        if (!isset($this->graph[$from])) {
            $this->graph[$from] = [];
        }
        $this->graph[$from][] = ['to' => $to, 'weight' => $weight];
    }
    
    // より効率的な実装...
}

実際の業務での応用例

ケース1: 物流システムでの配送コスト最適化

ある物流会社のシステム構築では、以下の要素を考慮した最短経路を求める必要がありました：

• 燃料費（正のコスト）
• 高速道路料金（正のコスト）
• 提携企業での割引（負のコスト）
• 帰り荷によるコスト削減（負のコスト）

結果として、従来の手動計算と比較して配送コストを平均15%削減することができました。

ケース2: ネットワークルーティングの最適化

ネットワーク機器メーカーのルーティングアルゴリズム開発では：

• 通常の回線コスト（正の重み）
• 優先回線による割引（負の重み）
• 混雑による追加コスト（動的に変化）

を考慮したルーティングテーブルの生成に活用しました。

パフォーマンス最適化のテクニック

SPFA（Shortest Path Faster Algorithm）の実装

ベルマンフォード法の改良版として、より高速なSPFAを実装することも可能です：

class SPFA {
    public function findShortestPath($graph, $start) {
        $vertices = count($graph);
        $distance = array_fill(0, $vertices, PHP_INT_MAX);
        $inQueue = array_fill(0, $vertices, false);
        $count = array_fill(0, $vertices, 0);
        
        $queue = new SplQueue();
        $distance[$start] = 0;
        $queue->enqueue($start);
        $inQueue[$start] = true;
        
        while (!$queue->isEmpty()) {
            $u = $queue->dequeue();
            $inQueue[$u] = false;
            
            foreach ($graph[$u] as $edge) {
                $v = $edge['to'];
                $w = $edge['weight'];
                
                if ($distance[$u] + $w < $distance[$v]) {
                    $distance[$v] = $distance[$u] + $w;
                    
                    if (!$inQueue[$v]) {
                        $queue->enqueue($v);
                        $inQueue[$v] = true;
                        $count[$v]++;
                        
                        // 負閉路検出
                        if ($count[$v] >= $vertices) {
                            throw new Exception('負閉路が検出されました');
                        }
                    }
                }
            }
        }
        
        return $distance;
    }
}

まとめ：ベルマンフォード法を業務で活用するために

ベルマンフォード法は、負の重みを含むグラフの最短経路問題を解決する強力なアルゴリズムです。適切に実装・最適化することで、物流最適化、ネットワークルーティング、ゲーム開発など、様々な分野で活用できます。

重要なポイントを整理すると：

メリット:

• 負の重みを持つ辺に対応
• 負閉路の検出が可能
• 実装が比較的シンプル

注意点:

• 計算量が O(VE) と大きい
• 大規模グラフでは最適化が必要
• 負閉路検出の実装を忘れがち

実際の業務では、要件に応じてダイクストラ法との使い分けや、SPFAなどの最適化手法の検討も重要になります。

次のステップ

ベルマンフォード法を実際のプロジェクトで活用するために、以下の手順で進めることをお勧めします：

もし実装や最適化でお困りのことがございましたら、お気軽にご相談ください。Fivenine Designでは、アルゴリズムの実装から大規模システムでの最適化まで、豊富な経験をもとにサポートいたします。