ベルマン–フォード法

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

ベルマン–フォード法は、重み付き有向グラフにおいて、単一の始点から他のすべての頂点への最短経路を求めるアルゴリズムの一つです。このアルゴリズムの大きな特徴は、辺の重みに負の数が含まれていても正しく動作する点です。もし辺の重みが全て非負数であれば、ダイクストラ法の方が効率的ですが、負の重みを持つ辺が存在する場合は、ベルマン–フォード法が有効な選択肢となります。

負閉路の検出

グラフ内に「負閉路」、すなわち辺の重みの合計が負になるような閉路が存在する場合、経路の重みをいくらでも小さくできるため、最短経路は定まりません。ベルマン–フォード法は、このような負閉路が始点から到達可能な場合に、その存在を検出し、報告することができます。

アルゴリズムの仕組み

ベルマン–フォード法の基本的な考え方は、以下の通りです。

1. 初期化: 始点以外のすべての頂点への距離を無限大に設定します。始点自身の距離は0です。
2. 緩和: グラフの全ての辺に対して、以下の処理を|V|-1回繰り返します。ここで|V|は頂点の数です。
- 辺(u, v)について、もしvまでの現在の距離が、uまでの距離と辺(u, v)の重みの合計よりも大きい場合、vまでの距離を更新します。
3. 負閉路の検出: 全ての辺に対して、緩和処理をもう一度行い、もし距離が更新される辺が存在すれば、グラフに負閉路が存在することを意味します。

アルゴリズムの擬似コード

procedure BellmanFord(list vertices, list edges, vertex source)
// Step 1: グラフの初期化
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null

// Step 2: 辺の緩和を反復
for i from 1 to size(vertices) - 1:
for each edge uv in edges:
u := uv.source
v := uv.destination
if v.distance > u.distance + uv.weight:
v.distance := u.distance + uv.weight
v.predecessor := u

// Step 3: 負の重みの閉路がないかチェック
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"

計算量

ベルマン–フォード法の計算量はO(|V|·|E|)です。ここで|V|は頂点の数、|E|は辺の数です。

正当性の証明

アルゴリズムの正当性は数学的帰納法によって証明できます。

• - 帰納法の基本ケース: i=0の場合、始点の距離は0で、他の頂点の距離は無限大であるため、条件は満たされます。
• - 帰納ステップ: i回目の反復で頂点vの距離が更新された場合、それは始点からvへの経路が存在することを意味します。また、i回目の反復後には、始点からvまでの高々i個の辺からなる最短経路が求められています。

負の閉路がない場合、最短経路上の各頂点は高々1回しか現れません。したがって、|V|-1回の反復で、最短経路はグラフ全体に伝播します。それ以上の短縮は不可能であり、負の閉路が存在しないことが保証されます。

応用

ベルマン–フォード法は、ネットワークルーティングプロトコルであるRIP（Routing Information Protocol）のような距離ベクトル型ルーティングプロトコルで利用されています。この場合、各ノード（ルーター）は自身の距離情報を隣接ノードに送り、受け取った情報に基づいて自身のルーティングテーブルを更新します。

問題点

ベルマン–フォード法には、以下のようないくつかの欠点があります。

• - スケーラビリティが低い
• - ネットワーク構成の変更への対応が遅い
• - 無限カウントの問題（リンク障害時に到達不能なノードへの距離推定が無限に増大し、ルーティングループを引き起こす可能性がある）

Yenの改良

Yenは、ベルマン–フォード法の効率を向上させるための改良版を提案しました。この改良では、頂点に線形の順序を割り当て、辺の集合を2つの部分集合に分割します。そして、頂点を特定の順序で見ていき、対応する辺を緩和することで、計算に必要な経路数を減らします。

まとめ

ベルマン–フォード法は、負の重みを持つ辺を扱うことができる汎用的な最短経路アルゴリズムです。負閉路の検出や、ルーティングプロトコルへの応用など、様々な分野で利用されています。しかし、その計算量やスケーラビリティには注意が必要です。

もう一度検索