【べるまんふぉーどほう】
ベルマンフォード法 とは？
最終更新:
💡 負の辺も扱える。負の閉路は別に判定
単一の始点からの最短経路を、辺の距離更新を繰り返して求める方法。負の辺と負の閉路の違い、到達可能性、基本形の計算量を具体例で解説します。
📌 このページのポイント
- 始点から到達できる頂点への距離を求める
- 負の辺は扱えるが、影響する負の閉路には有限の最短値がない
- 基本形は全辺の緩和を最大V−1回行い、追加の走査で閉路を確認
- 基本形の時間計算量はO(VE)。Vは頂点数、Eは辺数
ひよこ 負の辺があっても、最短経路を求められる？
ペンギン先生 ベルマンフォード法は負の重みの辺を扱えるよ。ただし始点から到達できる負の閉路があると、その閉路を何周もして値を小さくできる。影響を受ける頂点には有限の最短値がないんだ。
ひよこ 負の辺と負の閉路は違う？
ペンギン先生 違うよ。たとえばA→Bが4、B→Cが−2なら、A→B→Cの合計は2。負の辺があるだけで計算不能にはならない。閉路は一周して同じ頂点へ戻る経路で、その合計が負かを考えるんだ。
ひよこ どうやって距離を更新する？
ペンギン先生 始点を0、ほかを未到達として始めるよ。到達済みのuから辺u→vを通る値が今のvの距離より小さければ更新する。これを緩和と呼ぶ。全辺を走査する基本形で繰り返すんだ。
ひよこ 何回繰り返せば終わる？
ペンギン先生 影響する負の閉路がなければ、最短経路は最大V−1本の辺で表せるので、最大V−1回の走査で求められるよ。追加の走査で到達済みの頂点からまだ改善できるなら、始点から到達する負の閉路がある。変化がないときは早く終える実装もある。
ひよこ グラフのどこかに負の閉路があれば、全部失敗？
ペンギン先生 始点から届かない閉路は、この探索では検出されないよ。届く閉路があっても、影響を受けない頂点をどう扱うかは実装の契約による。基本形の時間はO(VE)。非負の辺に使う典型的なダイクストラ法などと、条件や実装を比較しよう。
もっと詳しく知りたい人へ
到達できない頂点の距離は0？
0ではありません。通常は無限大などで未到達を表し、そこから緩和しません。大きな整数を無限大の代わりに使うなら、加算のオーバーフローも避けます。
無向の負の辺もそのまま使える？
各無向辺を両向きの有向辺として扱い、繰り返し通ることを許すと、負の辺を往復するだけで負の閉路になります。辺を一度だけ使う問題などとは条件が異なります。
まとめ：ざっくりこれだけ覚えればOK！
「ベルマンフォード法」って出てきたら「辺を通った方が短ければ距離を更新し、最短経路を探す方法」と思えばだいたいOK！到達できる負の閉路がある場合は、有限の最短距離がないこともあるよ。
📖 おまけ：英語の意味
「Bellman–Ford algorithm」 ＝ ベルマン・フォード法
💬 負の重みを許す単一始点の最短経路問題で使うアルゴリズムの名前です。ここでの距離は道路の長さに限らず、辺に与えるコストを表します。