Bellman-Ford 法

Bellman-Ford 法は、負の辺を許す重み付き有向グラフで単一始点最短距離を求める。全辺の緩和を最大 V−1 回繰り返し、もう一回検査する。まだ改善できれば、始点から到達可能な負閉路があり、その閉路と下流の頂点には有限の最短距離がない。

一回の走査で、少なくとも経路の一辺分だけ情報が進む。辺の順序がよければ、同じ走査でさらに先へ進める。後半の辺がある頂点の距離を下げ、その頂点の出辺を既に調べ終えていた場合、次の走査で旧値に依存する結果を直す。この修正が繰り返しの役割だ。

Dijkstra 法は最小距離を確定して探索を減らすが、負辺はその保証を壊す。Bellman-Ford 法は途中で距離を確定しないので、遅れて現れた安い経路も反映できる。Dijkstra の罠プリセットは、Dijkstra 法が誤る同じグラフを正しく解く。代価は最悪 O(V·E) 時間。非負辺なら通常 Dijkstra 法を選び、負辺や負閉路検出が必要なら本手法を使う。

Bellman-Ford 法の仕組み

状態は dist と prev。前者は現在の最小コストで、始点が 0、他は ∞。後者は現在の最良経路の前駆頂点だ。優先度付きキューも確定済み集合もなく、辺を宣言順のリストに保持する。

一回の走査で全辺を順番に調べる。重み w の u → v で、u が未到達ならスキップする。それ以外は dist[u] + w < dist[v] を調べ、成立すれば距離と prev[v] = u を更新する。改善しない検査では何も変えない。

到達可能な負閉路がなければ、最短経路として単純路を選べ、その辺数は高々 V−1。本走査の k 回後には、高々 k 辺で得られる最短経路の情報が伝わるため、V−1 回で十分になる。一回全体で更新がなければ、以後の検査の入力も変わらず、早期終了できる。

最後にもう一回検査する。単純路の情報が伝わった後も距離が下がるなら、到達可能な負閉路がある。一周でコストが下がり、繰り返すと下限がなくなる。本実装は None を返し、有限の最短距離一式を出すことを拒否する。始点から到達できない負閉路は検出されず、その始点の答えにも影響しない。到達可能な負閉路が影響するのは閉路上とその下流であり、全頂点が必ず影響を受けるわけではない。

Bellman-Ford 法のステップ

既定の伝播プリセットは A–E の五頂点で、A から始める。六辺を毎回 A→B (4)、A→C (3)、B→D (3)、B→E (2)、C→B (−2)、D→E (2) の順に調べる。B の出辺は、B を改善する辺より前にある。

一回目：

1. A→B：0+4=4 < ∞ なので B は 4。
2. A→C：0+3=3 < ∞ なので C は 3。
3. B→D：4+3=7 < ∞ なので D は 7。この値は B の 4 に依存する。
4. B→E：4+2=6 < ∞ なので E は 6。同じ旧 B に依存する。
5. C→B：3+(−2)=1 < 4 で B を 1 に下げる。負辺も通常の更新だが、D と E は既に旧値を使っている。
6. D→E：7+2=9 ≥ 6 なので変更しない。更新は計五回。

二回目：

1. A→B の 4 は 1 以上、A→C の 3 は 3 と同じなので変更しない。
2. B→D：1+3=4 < 7 で D を 4 に下げる。前回は B の出辺を調べ終えていたため、今回修正する。
3. B→E：1+2=3 < 6 で E を 3 に下げる。
4. C→B と D→E は変更しない。更新は計二回。

三回目： 六辺全てで変更がなく、距離が安定したと分かる。四回目を省く。

検査走査： 六辺をもう一度調べても改善せず、始点から到達可能な負閉路はない。結果は A=0, B=1, C=3, D=4, E=3。

画面では実行中の全頂点を暫定状態の琥珀色に保ち、最後に五頂点をまとめて確定する。下部の辺リストは動かず、カーソルが毎回走査する。距離順に辺を選び直すことはない。

負閉路プリセットでは B→C→D→B の総重みが −1。dist[B] は毎回一ずつ下がり、各パスの終わりで 0、−1、−2 となる（最初のパスでは A→B で 1 になった後、同じ走査の D→B で 0 に下がる）。検査でも改善が続くので閉路が赤くなり、有限の答えなしで終了する。赤い閉路はアルゴリズムの prev ポインターから取り出しており、手で注釈したものではない。

時間計算量と空間計算量

一走査は E 辺を一辺 O(1) で調べる。最良時も有効な走査、更新なしの確認、検査を行うが、走査時間は O(E) のまま。全頂点の初期化と出力まで数えるなら O(V) を加える。dist と prev は O(V) で、キューはない。非負グラフでは Dijkstra 法の O((V+E) log V) が通常よい最悪上界を持つが、全入力で実操作数が必ず少ないという意味ではない。

境界ケース

• 負辺は通常どおり緩和する。ただし始点側の距離が有限である必要があり、未到達頂点からは伝播しない。
• 到達可能な負閉路は、その上と下流の距離を下限なしにする。検出して報告する必要がある。
• 未到達頂点は ∞ のままで、そこからの辺をスキップする。
• 辺の順序は収束回数を変えるが、到達可能な負閉路がなければ最終距離を変えない。よい順序なら一回、悪い順序なら V−1 回かかりうる。
• 一頂点で辺がなければ緩和も検査も空で、始点の距離は 0。

よくある間違い

1. 未到達の検査を省く。 浮動小数の ∞ では問題が隠れても、整数の番兵 INT_MAX + w はオーバーフローしうる。表示コードの u in dist は既存の経路だけを延長するための条件だ。
2. 一回で距離を確定する。 既定例の D は最初 7 だが正解は 4。一走査で更新がないことが安定の証明になる。
3. 負閉路を早く判定する。 V−1 回より前の改善は通常の伝播かもしれず、負閉路の根拠にならない。
4. 走査回数を一つ間違える。 V−1 回未満では最長の単純路の最後の一辺が届かないことがある。追加の検査走査と通常の緩和走査を区別する。
5. 不要なのに非負グラフで使う。 本手法の用途は負辺、負閉路検出、分散ルーティングなど反復緩和で情報を伝える場面にある。