ベルマン–フォード法
ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。
グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。
ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」[2]。G を負閉路を含むグラフとしよう。最短経路問題のとあるNP完全な変種で、G における辺の重複を許さない（負閉路を含む）最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。
アルゴリズム 編集
ベルマン–フォード法の基本構造はダイクストラ法とよく似ているが、ダイクストラ法が総当り的に未処理の重みが最小のノードを選択して緩めるのに対して、ベルマン–フォード法は頂点数を |V|としたとき、全辺を緩めることを単に|V| − 1 回繰り返す（初期状態で始点以外の頂点の始点からの距離は無限大にしておき、処理の途中段階で各頂点の始点からの最短距離と思われる距離に置き換えていく。これを relaxing（=「緩める」「緩和」など）と称する。負の閉路がなければ最短経路上の各頂点は高々1回しか出現しないので、反復によって最短距離が正確にグラフ全体に伝播する。重みが正であることを前提とした構造上の仮定に基づく貪欲法的手法とは異なり、この直接的な方法はより汎用的である。
ベルマン–フォード法の実行時間は O(|V|·|E|) で、|V|と|E|はそれぞれ頂点数と辺数である。
procedure BellmanFord(list vertices, list edges, vertex source)
// この実装では、グラフを頂点のリストと辺のリストで表す。
// そして、各頂点の distance と predecessor 属性が
// 最短経路を格納するよう変更していく。
// 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: // uv は u から v に向かう辺
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"
正しさの証明 編集
このアルゴリズムの正しさは数学的帰納法で示すことができる。以下にそれを示す。
補題: for サイクルを i 回繰り返したとき:
- Distance(u) が無限大でないとき、その値は s から u の何らかの経路の距離と等しい。
- 高々 i 個の辺からなる s から u への経路があるとき、Distance(u) は高々 i 個の辺から成る s から u への高々最短経路の距離である。
証明: 帰納法の基本ケースとして、i=0 で for サイクルを実行する前の時点を考える。すると、始点については source.distance = 0 であるから正しい。他の頂点 u については u.distance = infinity なので、これも正しい（0個の辺からなる始点から u への経路は存在しない）。
帰納ケースについては、まず第1の部分を証明する。ある頂点の距離が v.distance := u.distance + uv.weight で更新された時点を考える。帰納法上の前提により、u.distance は始点から u へのなんらかの経路の距離である。したがって u.distance + uv.weight は始点から u までの経路の長さと、そこから v までの距離を加えたもので、始点から v までの経路の距離である。
第2の部分については、高々 i 個の辺からなる始点から u への最短経路を考える。v が その経路上 u の直前の頂点だとする。すると、始点から v までの経路は高々 i-1 個の辺からなる始点から v までの最短経路となる。帰納法上の前提により、i-1 回の反復後の v.distance は高々この経路の距離である。したがって、uv.weight + v.distance は高々 s から u への経路の距離である。i-番目の反復で、u.distance は uv.weight + v.distance と比較され、uv.weight + v.distance の方が小さければその値が設定される。したがって、i 回の反復後、u.distance は高々始点から uへの最短経路の距離であり、その経路には高々 i 個の辺がある。
負の重みの閉路がないなら、それぞれの最短経路には各頂点は高々1回出現する。したがって step 3 に至ったとき、それ以上の経路や距離の短縮は不可能である。逆に短縮できないとすると、頂点 v[0],..,v[k-1] の任意の閉路について、次が成り立つ。
v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight
閉路上で総和を求めると、v[i].distance の項と v[i-1 (mod k)].distance の項は相殺され、次の式が残る。
0 <= v[i-1 (mod k)]v[i].weight の 1 から k までの総和
すなわち、全ての閉路は負でない重みを持つ。
応用 編集
ベルマン-フォード法の分散版は、Routing Information Protocol (RIP) などの距離ベクトル型ルーティングプロトコルで使われている。分散版にするのは、典型的にはISPが保有するIPネットワーク群の集合体のように、自律システム (AS) 内の複数のノード（ルーター）が関与するためである。これは次のステップで構成される。
- 各ノードは自身とAS内の他の全ノードとの距離を計算し、その情報をテーブルに格納する。
- 各ノードはそのテーブルを隣接する全ノードに送る。
- 隣接ノードから距離テーブルを受け取ると、他の全ノードへの最短経路を計算し、自身のテーブルを適宜更新する。
このときのベルマン-フォード法の主な欠点は次の通りである。
Yenによる改良 編集
1970年、Yenはベルマン-フォード法の改良を発表した[3]。Yenの改良は、まず全頂点に何らかの線型な順序を割り当て、全辺の集合を2つの部分集合に分割する。第1の部分集合 Ef は i < j となる全ての辺 (vi, vj) を含み、第2の部分集合 Eb は i > j となる辺 (vi, vj) を含む。そして頂点を v1, v2,...,v|V| の順に見ていき、その頂点から出ている Ef 内の辺を緩和させる。次に v|V|, v|V|-1,...,v1 という順序で頂点を見ていき、その頂点から出ている Eb 内の辺を緩和させる。Yenの改良は単一始点の最短経路問題で調べる必要のある経路数を事実上半減させる。
脚注・出典 編集
- ^ Dimitri P. Bertsekas (1992年3月). “A Simple and Fast Label Correcting Algorithm for Shortest Paths” (PDF). Networks, Vol. 23, pp. 703–709, 1993. 2008年10月1日閲覧。
- ^ Robert Sedgewick. Algorithms in Java. Third Edition. ISBN 0-201-36121-3. Section 21.7: Negative Edge Weights. http://safari.oreilly.com/0201361213/ch21lev1sec7
- ^ Jin Y. Yen. "An algorithm for Finding Shortest Routes from all Source Nodes to a Given Destination in General Network", Quart. Appl. Math., 27, 1970, 526–530.
参考文献 編集
- Richard Bellman: On a Routing Problem, in Quarterly of Applied Mathematics, 16(1), pp.87-90, 1958.
- L. R. Ford, Jr., D. R. Fulkerson: Flows in Networks, Princeton University Press, 1962.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman-Ford algorithm, pp.588–592. Problem 24-1, pp.614–615.
外部リンク 編集
- 対話型Javaアプレットによるデモ
- Cのコード例
- annas オープンソースのJava用グラフパッケージ。ベルマン-フォード法もある。