ベルマン–フォード法
最短経路の問題には、経路を安くするエッジがあることがあります。払い戻し、下り坂、有利な為替レートなどです。ダイクストラ法はこれに対応できません。ベルマン–フォード法は、賢さの代わりに根気を使って対応します。
考え方
最短経路のアルゴリズムはどれも、エッジの緩和という1つの操作に頼っています。u まで行ってからエッジ u → v を進むほうが、v へのこれまでの最良の道より短ければ、そちらを使います。ダイクストラ法は各エッジを1回ずつ、負のエッジがないときにだけ通用する賢い順序で緩和します。ベルマン–フォード法はそのような仮定をしません。距離が変わらなくなるまで、どんな固定の順序でもよいので、すべてのエッジを何度も緩和します。
ステップごとに
スタートの距離を 0、他のノードをすべて無限大にします。ノードが n 個なら n − 1 回繰り返します。すべてのエッジ u → v を見て、u に距離があれば緩和します。1回のパスで何も変わらなければ早めに終えます。その後、もう1回パスを行います。まだ緩和できるエッジがあれば、合計が負の閉路にスタートからたどり着けます。そうでなければ、どの距離も最短で、記録したノードが経路を示します。
例
長さ 4 の A → B、5 の A → C、2 の B → D、−3 の C → B という一方向のエッジを、この順に A から調べます。パス 1 で B は 4、C は 5、D は 6 になり、続いて C → B で B は 5 − 3 = 2 に下がります。パス 2 で D は 2 + 2 = 4 に下がります。パス 3 では何も変わらないので、答えは B 2、C 5、D 4 です。ダイクストラ法なら、負のエッジを見る前に B を 4、D を 6 で確定していたでしょう。長さ −4 のエッジ D → C を加えると、閉路 C → B → D → C の合計は −5 になります。パスのたびに距離がまた下がり、確認のパスがそれを報告します。
n − 1 回のパスで足りる理由
最短経路が存在するなら、同じノードを繰り返し通らないので、エッジは n − 1 本以下です。1回のパスですべてのエッジを緩和すると、エッジの順序がどうであれ、正しくわかっている最短経路はどれもエッジ1本分伸びます。そのためパス k の後にはエッジが k 本以下の最短経路がすべて正しく、n − 1 回のパスの後にはすべてが正しくなります。それでも順序は速さに影響し、よい順序なら1〜2回のパスで終わることもあります。
歴史と用途
この方法は1955年にアルフォンソ・シンベル(Alfonso Shimbel)、1956年にレスター・フォード・ジュニア(Lester Ford Jr.)、1957年にエドワード・F・ムーア(Edward F. Moore)、1958年にリチャード・ベルマン(Richard Bellman)が示しました。名前はそのうちのベルマンとフォードにちなみます。パスは各ルーターが単独で実行できるため、RIP などの距離ベクトル型ルーティングプロトコルの基礎になりました。金融では、為替レートの対数にマイナスを付けると、利益の出る一連の通貨取引(裁定取引)が負の閉路になり、ベルマン–フォード法で見つけられます。
試してみよう
アプリを開いて「ステップ」を押します。エッジはすべて一方向で、長さが負のものもあります。各ステップで固定の順序でエッジを1本調べ、タイルには今のパスと、そのパスで変わった距離の数が表示されます。たいていはすぐに何も変わらないパスが来て、探索は早めに終わります。「負の閉路を追加」にチェックを入れると、パスのたびに距離が下がり続け、最後に確認のパスが閉路を見つけて赤で描く様子が見られます。
よくある質問
ベルマン–フォード法の計算量は?
ノード数 V、エッジ数 E に対して O(V · E) です。パスは最大 V − 1 回で、各パスですべてのエッジを調べます。早めに終える工夫により実際にはずっと速いことが多く、最良の場合はパス1回で足ります。
負の閉路とは何ですか?
エッジの長さの合計が 0 未満の閉路です。何度も回ると経路をいくらでも短くできるので、そこを通ってたどり着けるすべてのノードへの最短距離は定まりません。
ベルマン–フォード法は無向グラフでも使えますか?
負のエッジがない場合だけです。無向の負のエッジは行き来できるので、それ自体が2本のエッジからなる負の閉路になります。負でないエッジなら使えますが、ダイクストラ法のほうが速いです。
SPFA とは何ですか?
Shortest Path Faster Algorithm の略で、ベルマン–フォード法の一種です。キューを使い、距離が変わったばかりのノードから出るエッジだけを調べ直します。多くの場合ずっと速いですが、最悪の場合は同じです。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ベルマン–フォード法を試す