アルゴリズム・データ構造図鑑 · 基礎から応用へ

Bellman–Ford法:負の辺を許して距離を更新する

辺の緩和を繰り返し、V−1回という境界と始点から到達できる負の閉路を区別する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 負の辺があっても緩和できる
  2. 辺の走査順で途中経過は変わる
  3. V−1回と負の閉路
  4. 費用と数値表現を確かめる
  5. この記事をロゲイアに質問する理解を確かめる

負の辺があっても緩和できる

Bellman–Ford法は始点から各頂点への最短距離を求める方法で、負の重みを持つ辺を扱えます。d[s]=0、ほかは無限大として始め、辺u→vについてd[u]+wがd[v]より小さければ距離と前駆頂点を更新します。これが緩和です。有限な距離が得られていないuからは更新しません。Dijkstra法のように取り出した頂点の距離を直ちに確定させず、後の緩和で何度でも改善できる状態にしておくことが、負の辺を許す上で重要です。

辺の走査順で途中経過は変わる

辺s→aが4、s→bが5、a→bが−2なら、最終的な距離はaが4、bが2です。同じ一巡でもs→aをa→bより先に見る実装では、bまで一度で2へ更新できます。逆の順序なら次の巡回で改善される場合があります。このように配列をその場で更新する実装では、一巡が必ず一辺分の進展だけを表すとは限りません。辺数別の動的計画法の証明を使う場合と、実装の実際の更新順を追う場合の説明を区別しましょう。

V−1回と負の閉路

到達可能な負の閉路がなければ、最短路は頂点を繰り返さない形にでき、辺数は高々V−1です。全辺の緩和をV−1回行えば必要な改善を取り込めます。その後さらに改善できる辺があれば、始点から到達可能な負の閉路が存在します。始点から到達できない負の閉路は、この始点に対する最短距離を壊しません。また負の閉路が見つかっても、全頂点の答えが無意味になるわけではなく、その閉路を経由して到達できる先の距離が下へ際限なく改善されます。

費用と数値表現を確かめる

単純な全辺走査版の最悪時間はO(VE)、距離と前駆頂点の追加領域はO(V)です。一巡で更新がなければ早く終了できますが、待ち行列による改善版も最悪上界が自動で線形になるわけではありません。無限大に重みを足したり整数がオーバーフローしたりすると、存在しない改善を作ることがあります。浮動小数点では丸め誤差も考慮します。経路を復元する際は負の閉路がないことと到達可能性を確認し、前駆頂点を無制限にたどらないようにします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ