ベルマン・フォードアルゴリズム

ベルマン・フォードアルゴリズムは、重み付き有向グラフ内の単一の始点頂点から他のすべての頂点への最短経路を計算するアルゴリズムです。^{[ 1 ]}同じ問題に対するダイクストラ法 よりも遅いですが、エッジの重みの一部が負の数であるグラフを処理できるため、汎用性が高いです。^{[ 2 ]}このアルゴリズムは、最初にアルフォンソ・シンベル（1955年）によって提案されましたが、1958年と1956年にそれぞれ発表したリチャード・ベルマンとレスター・フォード・ジュニアにちなんで名付けられました。^{[ 3 ]}エドワード・F・ムーアも1959年にこのアルゴリズムの変種を発表しており、そのためベルマン・フォード・ムーアアルゴリズムと呼ばれることもあります。^{[ 1 ]} 

負のエッジ重みは、グラフのさまざまなアプリケーションで見られます。これが、このアルゴリズムが役立つ理由です。^{[ 4 ]} グラフに、始点から到達可能な「負のサイクル」（つまり、エッジの合計が負の値になるサイクル）が含まれている場合、最も安いパスはありません。負のサイクル上の点を持つパスは、負のサイクルをもう1回歩くことでより安くなります。このような場合、ベルマン・フォードアルゴリズムは負のサイクルを検出して報告できます。^{[ 1 ] [ 5 ]}

ダイクストラ法と同様に、ベルマン・フォード法は緩和法によって進行し、正しい距離の近似値をより良い近似値に置き換えていき、最終的に解に到達します。どちらのアルゴリズムでも、各頂点への近似距離は常に真の距離の過大評価であり、その古い値と新しく見つかったパスの長さの最小値に置き換えられます。^{[ 6 ]}

しかし、ダイクストラ法は優先度キューを使用して、まだ処理されていない最も近い頂点を貪欲に選択し、その頂点から出るすべてのエッジに対してこの緩和処理を実行します。対照的に、ベルマン・フォード法はすべてのエッジを緩和し、この処理を実行します。${\displaystyle |V|-1}$時代、${\displaystyle |V|}$はグラフの頂点の数です。^{[ 6 ]}

これらの繰り返し処理のたびに、正しく計算された距離を持つ頂点の数が増加し、最終的にはすべての頂点が正しい距離を持つことになります。この方法により、ベルマン・フォードアルゴリズムはダイクストラアルゴリズムよりも幅広い種類の入力に適用できます。中間結果と等しく短いパスの選択は、緩和されたエッジの順序に依存しますが、最終的な距離は同じままです。^{[ 6 ]}

ベルマン・フォードが走る${\displaystyle O(|V|\cdot |E|)}$時間、${\displaystyle |V|}$そして${\displaystyle |E|}$それぞれ頂点数と辺数を表します。

関数BellmanFord(頂点のリスト、エッジのリスト、頂点ソース)は// この実装は、頂点（整数 [0..n-1] で表される）とエッジのリストとして表現されたグラフを受け取り、// ソースから各頂点への最短経路を保持する2 つの配列（distance と predecessor）を埋めます。 距離 :=サイズnのリスト 先行要素 :=サイズnのリスト// ステップ 1: グラフを初期化する各頂点 v in verticesに対して // すべての頂点までの距離を無限大に初期化する distance[v] := inf // そしてnullの前任者を持つこと predecessor[v] := null // ソースから自身までの距離はゼロです distance[source] := 0 // ステップ 2: エッジを繰り返し緩和する| V |−1回繰り返す: エッジの重み wを持つ各エッジ (u, v)に対して、距離 [u] + w < 距離 [v]ならば distance[v] := distance[u] + w 前任者[v] := u // ステップ 3:各エッジ (u, v) の重みwについて負の重みサイクルをチェックします。もしdistance[u] + w < distance[v]ならば 前任者[v] := u // 負のサイクルが存在する。// サイクル上の頂点を見つける visited := falseで初期化されたサイズnのリスト visited[v] := true while not visited[u] do visited[u] := true u := predecessor[u] // u は負のサイクル内の頂点です。// サイクル自体を見つけます ncycle := [u] v := predecessor[u] while v != u do ncycle := concatenate([v], ncycle) v := predecessor[v] エラー「グラフに負の重みのサイクルが含まれています」、ncycle 戻り距離、predecess

簡単に言うと、このアルゴリズムは、始点までの距離を0に、その他のすべてのノードまでの距離を無限大に初期化します。そして、すべてのエッジについて、そのエッジを通ることで終点までの距離を短縮できる場合は、距離を新しいより小さい値に更新します。

アルゴリズムの中核は、ループごとにすべてのエッジを走査するループです。${\displaystyle i\leq |V|-1}$の終わりに${\displaystyle i}$任意の頂点vから、 predecessorに記録された先行経路をたどる- 番目の反復では、総重みが最大でdistance[v]である経路が得られ、さらにdistance[v]は、ソースからvまでの経路で最大でi 個のエッジを使用する経路の長さの下限です。

サイクルのない最長経路は${\displaystyle |V|-1}$エッジ、エッジをスキャンする必要があります${\displaystyle |V|-1}$すべてのノードに対して最短経路が見つかったことを確認するために、数回実行されます。すべてのエッジの最終スキャンが実行され、距離が更新された場合は、長さの経路が決定されます。${\displaystyle |V|}$グラフ内に少なくとも1つの負のサイクルが存在する場合にのみ発生するエッジが発見された。

ステップ3で見つかったエッジ(u, v)は負のサイクルから到達可能でなければなりませんが、必ずしもサイクル自体の一部である必要はありません。そのため、サイクルが検出されるまで先行ノードのパスを逆方向にたどる必要があります。上記の擬似コードでは、ブール配列( visited)を使用してサイクル上の頂点を見つけていますが、任意のサイクル検出アルゴリズムを使用してサイクル上の頂点を見つけることができます。

アルゴリズムを実装する際の一般的な改善策は、ステップ 2 の反復でエッジが緩和されない場合に早期に終了することです。これは、すべての最短経路が見つかり、したがって負のサイクルが存在しないことを意味します。この場合、アルゴリズムの複雑さは次のように軽減されます。${\displaystyle O(|V|\cdot |E|)}$に${\displaystyle O(l\cdot |E|)}$どこ${\displaystyle l}$は、グラフにおける最短経路の最大長です。

アルゴリズムの正しさは帰納法によって示すことができる：^{[ 2 ] [ 7 ]}

補題。forループをi回繰り返した後、

• Distance( u )が無限大でない場合、それはsからuへの何らかの経路の長さに等しい。
• sからuへの経路に最大でi個のエッジが存在する場合、Distance(u)は、 sからuへの最大でi個のエッジを持つ最短経路の長さ以下である。

証明。帰納法の基本ケースとして、 を考え、が初めて実行される直前の時点を考えます。すると、始点頂点 については となり、これi=0は正しいです。他の頂点uについては となり、これも正しいです。なぜなら、始点からuへの辺が 0 のパスは存在しないからです。source.distance = 0u.distance = infinity

帰納的なケースでは、まず最初の部分を証明します。頂点の距離が によって更新される瞬間を考えます 。帰納的仮定により、はソースからuへのパスの長さです。すると、 はソースからuへのパスをたどり 、その後vに向かうソースからvへのパスの長さになります。v.distance := u.distance + uv.weightu.distanceu.distance + uv.weight

2 番目の部分では、ソースからvまでの、最大i 個のエッジを持つ最短経路P (複数存在する可能性がある)を考えます。この経路でvの直前の最後の頂点をuとします。すると、ソースからuまでの経路の部分は、ソースからuまでの、最大i-1個のエッジを持つ最短経路になります。そうでなければ、ソースからuまでの、最大i -1 個のエッジを持つ、より厳密に短い経路が存在しなければならず、その経路にエッジuvを追加することで、最大i個のエッジを持ち、 Pより厳密に短い経路が得られることになりますが、これは矛盾です。帰納的仮定により、i −1 回の反復後、は、ソースからuまでのこの経路の長さまでとなります。したがって、は、最大でPの長さになります。i^番目の反復では、がと比較され、が小さい場合は、と等しくなります。したがって、 i回の反復後、は、最大でPの長さ、つまり、ソースからvまでの、最大でi個のエッジを使用する最短経路の長さになります。u.distanceuv.weight + u.distancev.distanceuv.weight + u.distanceuv.weight + u.distancev.distance

負の重みのサイクルがない場合、最短経路は各頂点を最大で 1 回しか訪れないため、ステップ 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 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

つまり、すべてのサイクルは非負の重みを持つ。

最短経路を見つけるためにこのアルゴリズムを使用する場合、負のサイクルの存在は問題となり、アルゴリズムが正しい答えを見つけることを妨げます。しかし、負のサイクルが見つかると終了するため、ベルマン・フォードアルゴリズムは、ネットワークフロー分析におけるサイクルキャンセル技術など、これが目的となるアプリケーションに使用できます。^{[ 1 ]}

ベルマン・フォードアルゴリズムの分散型は、例えばルーティング情報プロトコル（RIP）などの距離ベクトル型ルーティングプロトコルで使用されています。 ^{[ 8 ]}このアルゴリズムは、通常ISPが所有するIPネットワークの集合である自律システム（AS）内の多数のノード（ルータ）が関与するため、分散型となっています。このアルゴリズムは、以下の手順で構成されています。

1. 各ノードは、自身とAS内の他のすべてのノードとの間の距離を計算し、この情報をテーブルとして保存します。
2. 各ノードは自身のテーブルをすべての隣接ノードに送信する。
3. ノードは、近隣ノードから距離テーブルを受信すると、他のすべてのノードへの最短経路を計算し、変更を反映するように自身のテーブルを更新します。

この状況におけるベルマン・フォードアルゴリズムの主な欠点は以下のとおりです。

• 拡張性に乏しい。
• ネットワークトポロジーの変更は、更新がノードごとに伝播されるため、迅速には反映されません。
• リンクまたはノードの障害により、あるノードが他のノード群から到達不能になった場合、それらのノードは無限に時間をかけてそのノードまでの距離の推定値を徐々に増加させ続ける可能性があり、その間にルーティングループが発生する可能性があります。

ベルマン・フォードアルゴリズムは、実際には（最悪のケースではないが）改善される可能性がある。アルゴリズムのメインループの反復が変更を加えずに終了した場合、後続の反復ではそれ以上の変更は加えられないため、アルゴリズムを直ちに終了させることができるという観察に基づいている。この早期終了条件により、アルゴリズムの最悪ケースは変わらないものの、メインループは場合によっては| V |  −  1よりもはるかに少ない反復回数で済む可能性がある。以下の改善はすべて、${\displaystyle O(|V|\cdot |E|)}$最悪の場合の時間計算量。

ムーア (1959)が記述したベルマン・フォード アルゴリズムの変種は、アルゴリズムの各反復で実行する必要のある緩和ステップの数を減らします。頂点vから出るエッジが最後に緩和されてから距離値が変化していない場合、 vから出るエッジを 2 回緩和する必要はありません。このようにして、正しい距離値を持つ頂点の数が増えるにつれて、各反復で緩和する必要のある出エッジの数が減少し、密なグラフでは定数倍の時間短縮につながります。この変種は、出エッジを緩和する必要のある頂点のコレクションを保持し、エッジが緩和されたときにこのコレクションから頂点を削除し、緩和ステップによって距離値が変化する頂点をコレクションに追加することによって実装できます。中国では、このアルゴリズムは 1994 年に再発見した端 凡鼎によって「最短経路高速アルゴリズム」として普及しました。^{[ 9 ]}

Yen (1970)は Bellman–Ford アルゴリズムの別の改良について説明しました。彼の改良では、まずすべての頂点に任意の線形順序を割り当て、次にすべてのエッジの集合を 2 つのサブセットに分割します。最初のサブセットE _fには、 i < jとなるすべてのエッジ ( v _i、v _j ) が含まれます。2 番目のサブセットE _bには、 i > jとなるエッジ ( v _i、v _{j ) が含まれます。各頂点は、} v ₁、v ₂、 ...、v _{| V |}の順に訪問され、その頂点からの各出エッジがE _{f内で緩和されます。次に、各頂点は}、v _{| V |}、v _{| V |−1}、 ...、v ₁の順に訪問され、その頂点からの各出エッジがE _b内で緩和されます。アルゴリズムのメイン ループの最初の反復以降、各反復では、緩和された距離が正しい最短経路距離と一致するエッジの集合に、少なくとも 2 つのエッジが追加されます。1 つはE _fから、もう 1 つはE _bから追加されます。この修正により、アルゴリズムのメインループの最悪ケースの反復回数が| V | − 1から  ${\displaystyle |V|/2}$[ ^{10 ] [ 11 ]​}

Bannister & Eppstein (2012)による別の改良では、Yen の 2 番目の改良で使用されている頂点の任意の線形順序をランダムな順列に置き換えています。この変更により、Yen の改良における最悪のケース (最短経路のエッジが 2 つの部分集合E _fとE _bの間で厳密に交互に現れる場合) が発生する可能性が非常に低くなります。ランダムに順列された頂点順序を使用すると、メイン ループで必要となる反復回数の期待値は最大で${\displaystyle |V|/3}$[ ^{11 ]​}

ジョージタウン大学のファイネマン（2024）は、高い確率で実行される改良アルゴリズムを作成した。${\displaystyle {\tilde {O}}(|V|^{8/9}\cdot |E|)}$時間。ここで、${\displaystyle {\tilde {O}}}$これは、対数因子を隠蔽するビッグオー記法の変形です。