https://pydocument.hatenablog.com/entry/2023/04/30/002143

ベルマン・フォード法は、グラフ理論における最短経路問題を解くためのアルゴリズムの一つです。最短経路問題とは、与えられたグラフにおいて、特定の2頂点間の最短経路（パス）を見つける問題です。

ベルマン・フォード法の概要

ベルマン・フォード法は、1958年にリチャード・ベルマンとレスター・フォード・ジュニアによって発表されました。（Lester Ford Jr. の発表は1956年）このアルゴリズムの特徴は、グラフ中に負の重みを持つ辺が存在する場合でも最短経路を求められる点にあります。ただし、負の閉路（そのパス上の重みの合計が負になるような閉路）が存在する場合は、最短経路が定義できません（無限に小さくできるため）。

ダイクストラ法との比較

最短経路問題を解くアルゴリズムとして、ダイクストラ法もよく知られています。ダイクストラ法は、ベルマン・フォード法よりも高速に動作しますが、負の重みを持つ辺が存在するグラフには適用できません。

特徴	ベルマン・フォード法	ダイクストラ法
負の重みの辺	扱える	扱えない
負の閉路	検出可能（最短経路は存在しないと判定）	検出不可能
計算量（頂点数V、辺数E）	O(VE)	優先度付きキュー使用で O((E+V)logV) 、フィボナッチヒープ使用でO(E + VlogV)（実装依存）
用途	負の重みが存在しうるネットワークのルーティングプロトコルなど	負の重みが存在しない場合の最短経路探索（例：道路の経路探索）

pydocument.hatenablog.com

アルゴリズムの手順

ベルマン・フォード法は、以下の手順で最短経路を求めます。

初期化
- 始点となる頂点の距離を0に設定します。
- 他のすべての頂点の距離を無限大（現実的には十分大きな値）に設定します。
緩和処理の反復
- グラフ内のすべての辺に対して、「緩和」処理を最大で |V|-1 回繰り返します（Vは頂点数）。
  - 緩和処理とは: 辺 (u, v) について、始点から頂点uまでの現在の最短距離 + 辺(u, v)の重みが、始点から頂点vまでの現在の最短距離よりも小さい場合、頂点vの最短距離を更新する処理です。より具体的には、dist[u] + cost(u, v) < dist[v] ならば、dist[v] を dist[u] + cost(u, v) に更新します。 (cost(u, v) は辺(u, v)の重み、dist[x]は始点から頂点xまでの現在の最短距離)
なぜ |V|-1 回繰り返すのか
- 始点から他の任意の頂点への最短経路は、単純パス（同じ頂点を2度通らないパス）であると仮定できます。
- 単純パスに含まれる辺の数は、最大でも頂点数-1 (|V|-1) です。
- 1回の緩和処理で、少なくとも1つの頂点への最短距離が確定します（最短経路上にある頂点の順に）。
- したがって、最大|V|-1回の反復で、すべての頂点への最短距離が求まります。
- 実際には、|V|-1回繰り返す前にすべての頂点への最短距離が更新されなくなる場合があり、その時点で処理を打ち切ることができます。
負の閉路の検出
- 緩和処理をもう一度（|V|回目）すべての辺に対して行います。
- |V|回目の処理で、いずれかの頂点の距離が更新された場合、「負の閉路が存在する」と判定します。これは、負の閉路を通ることで距離を無限に小さくできるため、最短経路が一意に定まらないことを意味します。

具体例

以下のグラフを例に、ベルマン・フォード法の動作を説明します。始点はAとします。

    4     2
A ----> B ----> C
^       ^
|       |
1       3
|       |
D ----> E
    -2

初期化

頂点 A B C D E

距離 0 ∞ ∞ ∞ ∞
緩和処理（1回目の反復）
- A -> B: dist[B] = min(∞, 0 + 4) = 4
- A -> D: dist[D] = min(∞, 0 + 1) = 1
- B -> C: dist[C] = min(∞, 4 + 2) = 6
- B -> E: dist[E] = min(∞, 4 + 3) = 7
- D -> E: dist[E] = min(7, 1 + (-2)) = -1
この時点で、各頂点の距離は以下のようになります。

頂点 A B C D E

距離 0 4 6 1 -1
緩和処理（2回目以降の反復）

頂点数が5なので、緩和処理を合計4回(V-1)繰り返しますが、2回目以降の反復では、どの辺の緩和処理を行っても頂点の距離は更新されません。
負の閉路の検出(|V|回目の反復): 5回目の反復でも、どの頂点の距離も更新されないため、このグラフには負の閉路は存在しません。