概要
この記事では、ベルマンフォード法がなぜ全ての辺に対する緩和処理を高々$|V|-1$回反復することで最短路を求められるのかを説明します。
証明自体は参考文献1が詳しいですが、私は初見では後述の「ある考え方を見落としていた」ことが原因で理解しづらかったので、自分なりに証明の内容が「当たり前」だと感じる理解の仕方を書きたいと思います。
ベルマンフォード法をうろ覚えの方もいらっしゃると思うので、一通りの基本事項を記してからその点を説明したいと思います。
ベルマンフォード法とは
ベルマンフォード法は重み付き有向グラフにおける単一始点最短路問題を解くアルゴリズムの一種です。
特にベルマンフォード法では、重み付き有向グラフの中でも有向閉路（サイクル）を持ち、負の重みが存在する最も一般的な状況でも最短路を求めることができます。
ただし、始点から到達可能な負閉路（際限なく周回することで経路長を$-∞$にできる閉路）があった場合は最短路を算出できません（最短路がwell-definedされません）が、ベルマンフォード法は負閉路の存在を真偽値で返すことができます。
なお、辺の重みが全て非負の場合はより高速なダイクストラ法を適用できます。
また、有向閉路を持たない重み付き有向グラフはDAG (Directed Acyclic Graph) と呼ばれ、動的計画法でより高速に最短路を求められます。
| アルゴリズム | グラフの制約条件 | 計算量 |
|---|---|---|
| ベルマンフォード法 | 一般の重み付き有向グラフ | $O(|V||E|)$ |
| ダイクストラ法 | 全ての辺の重みが非負 | $O(|V|^2)$または$O(|E|log|V|)$ |
| 動的計画法 | DAG（閉路を持たない） | $O(|V|+|E|)$ |
※$|V|$: 頂点の数、$|E|$: 辺の数
ベルマンフォード法のアルゴリズム
| 記号 | 定義 |
|---|---|
| v | 頂点 |
| s | 始点 |
| d[v] | 始点から頂点vへの最短路長推定値（初期値INFで、実行時により小さな値に更新されていく） |
| d*[v] | 始点から頂点vへの最短路長 |
| w(u, v) | 頂点uから隣接する頂点vへの辺の重み |
| V | 頂点集合 |
| |V| | 頂点数 |
| E | 辺集合 |
| e(u, v) | 頂点uから隣接する頂点vに向かう辺 |
| w(u, v) | 辺e(u, v)の重み |
| ※INFは適当な大きな値（変数を格納する型の取り得る最大の整数値など） |
// 始点を0に、他の全ての頂点をINFに初期化する
d[s] = 0
for each vertex v in V
d[v] = INF
// |V|-1回の反復処理（**なぜここが|V|-1回でいいのかが本記事のテーマ**）
for i = 1 to |V| - 1
// 全ての辺に対して緩和処理を行う
for each edge e(u, v) in E
// 緩和処理（最短路長推定値d[v]でより小さな値が見つかったらその値に更新）
if d[v] > d[u] + w(u, v)
d[v] = d[u] + w(u, v)
// 最短路長だけでなく最短路となる頂点列も求める場合はここでuを記録すれば良い（本記事では省略）
// 負閉路の検出
for each edge e(u, v) in E
// 負閉路がある場合は|V|-1回の反復処理後もd[v]がより小さな値に更新される状態になっている
if d[v] > d[u] + w(u, v)
return false
return true
緩和処理とは、最短路長の推定値である$d[v]$を（より小さな値が見つかったらその値に）更新していく処理のことを言います。
なぜ緩和処理（relaxation）という名前がつけられているのかは参考文献1が詳しいですが、歴史的経緯が大きく、あまり気にする必要は無いかと思います。
図とアリゴリズムの実行例は以下のページがわかりやすいです。
https://www.programiz.com/dsa/bellman-ford-algorithm
なぜ高々|V|-1回の反復処理で最短路が求まるのか
ここから、なぜベルマンフォード法は全ての辺に対する緩和処理を高々$|V|-1$回反復すると（始点から）任意の頂点への最短路長が求まるのかを考えていきます。
まず、最短路について以下2つの性質が成り立つことに注意します。
- 性質1
- 最短路は同じ頂点を2回以上訪れる路を考える必要がなく、高々$|V|-1$個の辺しか通らないとしてよい
- 性質2
- 最短路$p(s, v_1^\ast, v_2^\ast, ..., v_k^\ast)$があったとして、辺$e(s,v_1^\ast), e(v_1^\ast,v_2^\ast), ...,e(v_{k-1}^\ast,v_k^\ast)$の順に緩和処理をすると、$d[v_k^\ast]$ = $d^\ast[v_k^\ast]$となる（始点$s$から頂点$v_k^\ast$への最短路長が求まる）
※単に$v_i$ではなく$v_i^\ast$と表記しているのは、これらがただの頂点番号ではなく、最短路の順に番号を振った頂点であることを強調するためです。（結局図は掲載しませんでしたが、図中の頂点番号との混同も避けたいため。）
性質1は、最短路であれば同じ頂点に戻ってくるような無駄な動きはしないということです。
（最短路が存在するとき負閉路は存在しないので、閉路長は必ず非負の値になります。したがって同じ頂点を2回以上訪れる路もその閉路長が0であれば最短路になり得ますが、そのような閉路を取り除いた路も必ず最短路なので、わざわざ閉路を考える必要がありません。）
性質2は、$s,v_1^\ast,v_2^\ast,...,v_k^\ast$の頂点の並びが最短路であることに注意すれば当たり前です。
なぜなら$p$が最短路であると仮定した以上、最短路は$s,v_1^\ast,v_2^\ast,...,v_k^\ast$の順に移動していくことが分かっているのですから、同じ順に緩和処理をしていけば必ず正しい最短路長が算出されます。
この場合、緩和処理と言っても単に$s,v_1^\ast,v_2^\ast,...,v_k^\ast$それぞれの間の辺の重みを足し算しているだけです。
最短路においてはその足し算の処理が緩和処理と同じ内容になり、その結果が最短路長になるということです。（形式的な証明は参考文献1を参照）
当たり前に感じるための考え方
さて、ここからの考え方が記事の本題です。（既に当たり前に感じることができる人にとっては私流の冗長な説明を尽くすことになります。）
参考文献1では上記の2つの性質より高々$|V|-1$回の反復処理で最短路長が求まると書かれています。
しかし、性質2はあくまで頂点の並びが最短路である場合に成り立つ話です。
なぜ、（アルゴリズム実行中は）最短路が未知であるベルマンフォード法で性質2が使えるのでしょうか？
これは「具体的な最短路が未知であっても、（負閉路が無ければ）必ずどこかに最短路が存在している」と考えることで理解できます。
つまり、全ての辺に対する緩和処理の1回の反復で、具体的に最短路がどこかは分からないが、どこかに存在する最短路の1つの頂点までの最短路長が確定する、ということです。
最短路に含まれる高々$|V|-1$個の（始点を除く）頂点までの最短路長が、始点に隣接する頂点から順に1個ずつ確定していくので、反復処理は高々$|V|-1$回で良いのです。
このことはどの頂点でも成り立つのですが、具体例として始点から離れたどれか一つの頂点を選んで、始点からその頂点への最短路が（具体的にどれなのかは分からなくても）どこかに存在することをイメージするとわかりやすいと思います。
（なお参考文献1でも、全ての辺に対するi回目の緩和処理の中に最短路となるi番目の辺が含まれる、とは書かれているので丁寧に読めば上記の内容はイメージできるようになっています。）
具体的な流れのイメージ
さらに、このことを具体的に順を追って書いてみます。
まず、1回目の反復処理で全ての辺の緩和処理が実施されるため、（当たり前ですが）始点$s$に隣接する頂点への辺は全て緩和処理されます。この頂点の中に、ある頂点$v_k^\ast$への最短路における$s$の次の頂点である$v_1^\ast$が含まれます。
なぜなら今考えているのは始点$s$からの最短路なのですから、最短路は必ず$s$から出発して次に$s$と隣接するいずれかの頂点に行くからです。
そのような$v_1^\ast$が具体的にどの頂点かはアルゴリズム実行完了まで分かりません（重みが全て非負なら確定してダイクストラ法が使えますが、ここでは負の重みが存在するため未知です）が、ともかくこれでどこかにある辺$(s,v_1^\ast)$の緩和処理によって$d[v_1^\ast]$が$d^\ast[v_1^\ast]$に確定したといえます。（くどいですが、具体的にどの頂点が確定したかは未知です。）
2回目の反復処理でもやはり全ての頂点の緩和処理を実施するため、具体的にどこかは分からないものの、（既に$d^\ast[v_1^\ast]$が確定している）$v_1^\ast$の次の頂点である$v_2^\ast$の緩和処理が完了し、$d^\ast[v_2^\ast]$が求まります。
これを繰り返すことで$d^\ast[v_k^\ast]$が求まります。
ここで、$(v_1^\ast,v_2^\ast...,v_k^\ast)$は性質1から高々$|V|-1$個しかありませんから、高々$|V|-1$回の反復処理で最短路長が求まるということになります。
また、最短路の終点である$v_k^\ast$としてどの頂点を選んでも同じ議論が成立するので、ベルマンフォード法の実行が完了すると全ての頂点に対する（始点$s$からの）最短路長が求まることになります。
性質2とのつながりのイメージ
最後にもう少し、性質2とこの考え方の結びつきを言語化するための補足をします。
性質2にはもう一つの重要なポイントがあって、それはこの順に実施されている緩和処理がありさえすれば最短路が求まるという点です。
ベルマンフォード法では毎回の反復処理で全ての辺の緩和処理が行われますが、その中のどれかが「順に実施されている緩和処理」に当てはまれば良いのです。
なのでグラフの構造によっては1回の反復処理でそのような順に緩和処理されることもあり得ますがまれなことで、一般のグラフ（ただし負閉路を持たない）では最悪のケースでも$|V|-1$回繰り返したらその順に当てはまる緩和処理の並びが必ず見つかります。
なお順番に当てはまらない緩和処理が混じっても問題ないと言えるのは、一度$d[v_i^\ast]$が$d^\ast[v_i^\ast]$になったらそこから$d[v_i^\ast]$の値が変化することは無いことに由来します。
終わりに
このようにして考えると、ベルマンフォード法で始点$s$から各頂点への最短路長が高々$|V|-1$回の反復処理で求まるのは当たり前のように感じられます。
個人的には性質1は当たり前、性質2はちょっと考えると当たり前、そして本記事の「考え方」もちょっと考えると当たり前の感覚です。
しかしこの「ちょっと考えると」が2つ挟まっていることで、初見でいきなり全体の結論だけ見ると当たり前の感覚を持てなかったです。
自分はこの2つの「ちょっと考えると」を順番に消化することで、全体の結論（記事のタイトル）も当たり前の感覚として消化できるようになりました。
また、このような思考の分解は、得意な人は暗黙的にやってしまっている（し文章にすると冗長な説明になってしまう）のでなかなか表に出てきませんが、できない人にとっては必要な情報なんじゃないかと思っています。
もしここに書いたのと同じ悩みを持っている人がいらっしゃいましたら是非参考にしてみてください。
※記事内容全体として文献2も参考とさせて頂きました。