ベルマンフォード法
辺の重みを編集し、各ラウンドで全辺を緩和して最短経路を求めます。負の辺があっても正しく動き、負閉路も検出します d[v] = min(d[v], d[u] + w)
辺の重み（負の値も設定できます。マイナスにすると赤く表示）
| 辺 | 重み w | 値 |
|---|
始点
A
ラウンド数 i
0 / |V|−1 = 4
このラウンドの更新数
—
状態
準備完了
距離 d[v]（始点 A からの暫定最短）
有向グラフ（緑=最短経路木の辺 / 赤=負の辺）
ベルマンフォード法は、始点から各頂点への最短経路を求めるアルゴリズムです。やることはシンプルで、すべての辺について「緩和（リラクゼーション）」を |V|−1 回くり返すだけ。
緩和とは、辺
Dijkstra 法より遅いものの、負の重みの辺を扱える点が強みです。さらに |V|−1 回の後にもう 1 回まわしてまだ更新が起きるなら、たどると無限に距離が下がる「負閉路」が存在すると判定できます。
緩和とは、辺
u → v（重み w）について d[u] + w < d[v] なら d[v] を d[u] + w に更新する操作です。これを全辺・全ラウンドで行うと最短距離に収束します。Dijkstra 法より遅いものの、負の重みの辺を扱える点が強みです。さらに |V|−1 回の後にもう 1 回まわしてまだ更新が起きるなら、たどると無限に距離が下がる「負閉路」が存在すると判定できます。
いま何が起きている？
ここがポイント
- 緩和を |V|−1 回 ── 各ラウンドで全辺を見て
d[v] = min(d[v], d[u]+w)。最短経路は高々 |V|−1 本の辺なので、この回数で収束する。 - 負の辺に強い ── 一度確定した距離を後から下げ直せるため、負の重みがあっても正しい最短距離を出せる。
- 負閉路の検出 ── |V|−1 回の後でもまだ更新できるなら、その先には負閉路があり「最短距離が存在しない（−∞）」とわかる。
- Dijkstra との違い ── Dijkstra は確定した距離を二度と更新しないので、負の辺があると誤る。比較トグルでその失敗を確かめられる。