Bellman–Ford法

同義語:Bellman-Ford法ベルマン–フォード法ベルマン・フォード法Bellman–FordのアルゴリズムBellman–Ford algorithmBellman-Ford algorithm

概要

Bellman–Ford法(Bellman–Ford algorithm)とは、辺の重みが負でもよい有向グラフで、1 つの頂点から各頂点への距離を求める手順であり、すべての辺を順に調べて暫定の値を下げることを、頂点の数より 1 回少ない回数だけくり返す。手間は頂点の数と辺の数の積に比例する。そのあとに値を下げられる辺が残ることと、始点から到達できる負の閉路があることは同値で、記録した直前の頂点をたどると最短路木や負の閉路が得られる。負の辺のある最短の道、差分制約の不等式の解法、付け替えの重みの計算、一周して増える交換の検出に使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 有向グラフ, Dijkstra法, 動的計画法, 数学的帰納法

Bellman–Ford法(Bellman–Ford algorithm)は、辺の重みが負でもよい有向グラフで、1 つの頂点から各頂点への最短の歩道の重みを求める手順である。すべての辺を順に調べて暫定の値を下げることを、頂点の個数より 1 回少ない回数だけくり返す。
Dijkstra法 は、暫定値が最小の頂点を確定していく手順で、確定が正しいのは辺の長さが $0$ 以上だからである。負の辺があると、確定した頂点にあとからもっと短い歩道が見つかることがある(Dijkstra法 の節「負の長さの辺」)。Bellman–Ford法は確定をやめる。どの頂点の値も、最後まで書き換えてよい暫定値のままにしておき、全部の辺を調べ直す。遅くなる代わりに、負の辺があっても正しく、さらに、距離が定まらない原因である負の閉路を見つけられる。
この記事で計算すること・証明することは次のとおりである。

  • 手順が $O(nm)$ の手間で距離を求め、負の閉路の有無を判定すること(thm-bf-main)。$n$ は頂点の数、$m$ は辺の数である。
  • 直前の頂点の記録が最短路木になること(thm-bf-tree)。
  • 負の閉路があるとき、それを実際に取り出し(thm-bf-cycle)、距離が $-\infty$ になる頂点を求めること(prop-bf-infinity)。
  • 不等式の系 $x_v-x_u\le c(u,v)$ が Bellman–Ford法で解けること(thm-bf-diff)。
    手順の起源は 1 つではない。Shimbel が 1954 年に概略を述べ、Moore が 1957 年に詳しく述べ、Bellman が 1958 年に Ford の緩和の定式化を使って書いた(Eri19 §8.7、pp. 289–291)。辺の本数を添字に入れた再帰式 $d_k$ の正しさは 動的計画法 の定理「Bellman–Ford の再帰式」で証明されている。この記事は、配列 1 本を書き換えていく実際の手順の性質を扱う。配列を書き換える手順の値は $d_k$ と一致しないので(ex-bf-order)、証明は別に要る。

定義と使える条件

重み付き有向グラフと距離

$G=(V,E)$ を有限の有向グラフ($E\subset V\times V$、ループを許す)、$w\colon E\to\mathbb{R}$ を辺の 重み、$s\in V$ を 始点 とする。$n:=\lvert V\rvert$、$m:=\lvert E\rvert$ とする。
(a) 辺をたどる頂点の列 $v_0\to v_1\to\dots\to v_l$ を 歩道、その重み $\sum_{i}w(v_{i-1},v_i)$ を歩道の 重み という。$l=0$ の歩道の重みは $0$ である。同じ頂点を通らない歩道を 道 という。
(b) $v_0=v_l$、$l\ge1$ の歩道を 閉じた歩道 という。重みが負の閉じた歩道を 負の閉路 という。
(c) $s$ から $v$ への歩道の重みの下限を $\operatorname{dist}(v)\in\mathbb{R}\cup\{\pm\infty\}$ と書き、$v$ の 距離 という。歩道がなければ $+\infty$ である。

負の閉路を何度も回ると重みはいくらでも小さくなるので、距離は $-\infty$ になりうる。

距離が定まる条件

$\operatorname{dist}(v)=-\infty$ であることと、$s$ から到達でき、かつ $v$ に到達できる負の閉路があることは同値である。そうでなく $v$ が $s$ から到達できるとき、$\operatorname{dist}(v)$ は道の重みの最小値で、$n-1$ 本以下の辺の歩道で達成される。

閉じた部分を除く

そのような負の閉路があれば、$s$ から閉路へ行き、閉路を $k$ 回回って $v$ へ行く歩道の重みは $k\to\infty$ で $-\infty$ に発散する。
そのような負の閉路がないとする。$s$ から $v$ への歩道が同じ頂点を 2 度通れば、間の閉じた部分は $s$ から到達でき $v$ に到達できるので、重みは $0$ 以上である。これを除いても歩道は同じ端点をもち、重みは増えない。くり返すと道になるので、歩道の重みの下限は有限個の道の重みの最小値である。道の辺は $n-1$ 本以下である。$\square$

手順の中で使う語を定める。各頂点に暫定値 $d(v)\in\mathbb{R}\cup\{+\infty\}$ と直前の頂点 $p(v)$ を持たせる。

緊張と緩和

辺 $(u,v)$ が 緊張している(tense)とは、$d(u)< +\infty$ かつ $d(u)+w(u,v)< d(v)$ であることをいう。緊張した辺の 緩和(relaxation)とは、$d(v):=d(u)+w(u,v)$、$p(v):=u$ と書き換えることをいう。
パス(pass)とは、辺全体を決めた順に 1 回ずつ調べ、その時点で緊張している辺を緩和する操作である。
Bellman–Ford法 とは、$d(s)=0$、$v\ne s$ で $d(v)=+\infty$、すべての $v$ で $p(v)$ を未定義とおき、パスを $n-1$ 回行う手順である。その途中で値の変わらないパスがあれば止めてよい。最後に緊張した辺が残っていれば負の閉路があると報告し、残っていなければ $d$ を距離として返す。

使える条件は次のとおりである。
(i) グラフは有向で有限である。向きのない辺は両向きの辺に直す(重みが負なら、それだけで負の閉路になる)。
(ii) 重みは実数ならよい。符号の条件はない。
(iii) 求めたいのは $s$ から到達できる範囲の距離である。到達できない負の閉路は影響せず、検出もされない。
(iv) 緩和は狭義の不等号で行う(ex-bf-counterexamples)。

公式の表

最短の道を求める手順の比較である。$h$ は、$s$ から到達できる頂点ごとに、最短の歩道の辺の本数の最小値をとり、それらの最大値をとった数である(負の閉路がないとき $h\le n-1$)。

手順重みの条件手間負の閉路根拠
Bellman–Ford法実数$O(nm)$判定と取り出しthm-bf-main、thm-bf-cycle
値が変わらなければ止める実数$O((h+1)m)$あれば値が変わり続けるので $n-1$ 回で打ち切るthm-bf-main
緊張の候補をキューで管理する(Moore)実数$O(nm)$負の閉路があれば止まらないprop-bf-moore、Eri19 §8.7、pp. 292–294
閉路のないグラフの順の計算実数、閉路なし$O(n+m)$起こらない動的計画法 の公式の表の有向非巡回グラフの行(重みの符号を変える)
Dijkstra法(二分ヒープ)$0$ 以上$O((n+m)\log n)$起こらないDijkstra法 の定理「二分ヒープによる Dijkstra 法の手間」
Johnson の方法(全頂点対)実数$O(n(n+m)\log n)$最初の 1 回で判定Eri19 §9.4、p. 312

手間は、加算と比較を 1 回の演算として数える。Dijkstra法 の定理「長さの付け替え」の $\varphi$ は、次の表の 2 行目で求まる。

使い方作るグラフ読み取り方根拠
距離そのまま$d(v)=\operatorname{dist}(v)$thm-bf-main
全頂点の負の閉路の判定、付け替えの $\varphi$新しい頂点 $q$ と重み $0$ の辺 $q\to v$ を足す$\varphi(v)=\operatorname{dist}(q,v)$thm-bf-diff
差分制約 $x_v-x_u\le c$辺 $u\to v$、重み $c$ と、上の $q$$x_v=\operatorname{dist}(q,v)$thm-bf-diff
掛け算の連鎖 $\prod r_i>1$ の検出重み $-\log r_i$負の閉路ex-bf-exchange

主定理と証明

手順の不変量

緩和の不変量

初期値から任意の順に緩和を行う。どの時点でも次が成り立つ。
(1) $d(v)$ は増えない。
(2) $d(v)< +\infty$ なら、$d(v)$ は $s$ から $v$ への歩道の重みである。
(3) $p(v)$ が定義されていれば、$u=p(v)$ について $d(u)< +\infty$ かつ $d(v)\ge d(u)+w(u,v)$ である。
(4) $d(v)< +\infty$ で $p(v)$ が未定義なら、$v=s$ かつ $d(s)=0$ である。

1 回の緩和で保たれることを見る
証明を開く

初期値では (1)〜(4) は明らかである。辺 $(u,v)$ の緩和で変わるのは $d(v)$ と $p(v)$ だけで、$d(v)$ は下がるので (1) が成り立つ。(2) は、$u$ への歩道に辺 $(u,v)$ をつなげばよい。

(3) を見る。緩和の前の $d(u)$ を $d_0$ とする。緩和のあとの $d(v)$ は $d_0+w(u,v)$ で、緩和のあとの $d(u)$ は $d_0$ 以下である($u=v$ のときも)。よって $v$ については成り立つ。$p(x)=v$ である別の頂点 $x$ については、$d(v)$ が下がっても不等式は保たれる。

(4) を見る。$p(v)$ は緩和で定義され、一度定義されれば未定義に戻らず、$d$ が有限になるのは最初の緩和のときである。よって $p(v)$ が未定義で $d(v)$ が有限なのは、一度も緩和されていない $s$ だけである。$\square$

緊張した辺がなくなれば終わり

ある時点で緊張した辺がないとする。このとき $s$ から到達できる負の閉路はなく、すべての $v$ で $d(v)=\operatorname{dist}(v)$ である。

$d(s)\le0$ は有限である。緊張していない辺 $(u,v)$ では、$d(u)$ が有限なら $d(v)\le d(u)+w(u,v)$ も有限である。歩道に沿ってたどると、$s$ から到達できる頂点の $d$ はすべて有限である。
$s$ から到達できる閉じた歩道 $v_0\to\dots\to v_l=v_0$ について、$d(v_i)\le d(v_{i-1})+w(v_{i-1},v_i)$ を $i=1,\dots,l$ で足すと、$d$ の和が打ち消し合い、$0\le\sum_iw(v_{i-1},v_i)$ を得る。よって負の閉路はない。
lem-bf-invariant の (2) より $d(s)$ は閉じた歩道か長さ $0$ の歩道の重みなので $d(s)\ge0$ で、$d(s)=0$ である。$s$ から $v$ への任意の歩道について、同じ不等式を足すと $d(v)\le d(s)+(\text{歩道の重み})$ である。これと (2) より $d(v)$ は歩道の重みの最小値である。到達できない $v$ では (2) より $d(v)=+\infty$ である。$\square$

正しさと回数

$d_k(v)$ を、$s$ から $v$ への辺が $k$ 本以下の歩道の重みの最小値とする(なければ $+\infty$)。

Bellman–Ford法の正しさ

辺を調べる順は任意とする。
(1) $k$ 回のパスのあと、すべての $v$ で $d(v)\le d_k(v)$ である。
(2) $s$ から到達できる負の閉路がなければ、$h$ 回のパスのあと $d=\operatorname{dist}$ となり、緊張した辺はない。
(3) $s$ から到達できる負の閉路があれば、どのパスのあとでも緊張した辺があり、どのパスでも値が変わる。
とくに、$n-1$ 回のパスのあと緊張した辺が残ることと、$s$ から到達できる負の閉路があることは同値であり、残らなければ $d=\operatorname{dist}$ である。手間は $O(nm)$ である。

パスの回数についての帰納法
  1. $k=0$ は初期値から成り立つ。$k\ge1$ とし、$k-1$ 回で成り立つとする。$d_k(v)$ が有限のとき、それを達成する歩道 $W$ をとる。$W$ が辺をもたなければ $v=s$ で、$d(s)\le0=d_k(s)$ である。$W$ の最後の辺を $(u,v)$ とすると、残りは辺が $k-1$ 本以下の歩道なので、$k$ 回目のパスの初めに $d(u)\le d_{k-1}(u)\le d_k(v)-w(u,v)$ である。パスが辺 $(u,v)$ を調べる直前の値を $d(u)$ と書くと、調べた直後の $d(v)$ は、緩和したかどうかによらず $d(u)+w(u,v)\le d_k(v)$ 以下である(ループ $u=v$ でも同じ)。$d$ は増えないので、これはパスの終わりまで保たれる。
  2. $h$ の定義と prop-bf-dist より $d_h=\operatorname{dist}$ である。(1) より $d\le\operatorname{dist}$、lem-bf-invariant の (2) より $d\ge\operatorname{dist}$ である。辺 $(u,v)$ で $\operatorname{dist}(u)$ が有限なら、歩道をつなぐと $\operatorname{dist}(v)\le\operatorname{dist}(u)+w(u,v)$ なので、緊張していない。
  3. lem-bf-fixed の対偶より、どの時点でも緊張した辺がある。パスの初めに緊張している辺 $(u,v)$ は、パスがそれを調べるまでに $d(v)$ が下がっているか、そのとき緩和される。$d(u)$ だけが下がっても緊張は解けないので、どちらにしてもそのパスで値が変わる。
    手間は、1 回のパスが $O(m)$、最後の検査が $O(m)$ である。$\square$

パスの回数の $n-1$ は減らせない。最短の道の辺を後ろから順に調べる順では、1 回のパスで 1 頂点しか進まない(ex-bf-counterexamples)。逆に、最短路木の辺を根に近い順に先に調べる順なら 1 回で済む(ex-bf-order)。

最短路木

$p$ を、辺 $p(v)\to v$ の集まり($p(v)$ が定義された $v$ 全体)とみる。これを 直前の頂点のグラフ という。

直前の頂点のグラフの閉路
  1. どの時点でも、直前の頂点のグラフの閉路は負の閉路である。
  2. $s$ から到達できる負の閉路がなければ、手順の終わりに、直前の頂点のグラフは $s$ を根とする有向木で、頂点の集合は $s$ から到達できる頂点全体であり、木の中の $s$ から $v$ への道は最短である。
閉路ができる瞬間を見る
  1. 閉路を含む時点で、閉路の上の $p$ の値が最後に変わった緩和をとり、それを辺 $(u,v)$ の緩和とする。この緩和の直前には、閉路の残りの部分が $v=y_0\to y_1\to\dots\to y_k=u$ として直前の頂点のグラフにある。$k\ge1$ なら lem-bf-invariant の (3) より $d(y_i)$ はすべて有限で、$d(y_{i})\ge d(y_{i-1})+w(y_{i-1},y_i)$ である。これらを足すと $d(u)\ge d(v)+W$ である($W$ は道の重み。$k=0$ のときは $u=v$、$W=0$ で、同じ式が成り立つ)。緊張の条件 $d(u)+w(u,v)< d(v)$ と合わせると
    $$ d(v)+W+w(u,v)\le d(u)+w(u,v)< d(v) $$
    となる。$d(v)$ は有限なので $W+w(u,v)< 0$ であり、これは閉路の重みである。
  2. thm-bf-main の (2) より、終わりに $d=\operatorname{dist}$ である。(1) より直前の頂点のグラフに閉路はない。$d(s)=0$ で $s$ は緩和されないので、$p(s)$ は未定義である。$s$ から到達できる $v$ は $d(v)$ が有限なので、$p$ を逆にたどると、閉路がないので途中で止まり、lem-bf-invariant の (4) より止まる先は $s$ である。この道の重みを $W$ とすると、lem-bf-invariant の (3) を足して $d(v)\ge d(s)+W=W\ge\operatorname{dist}(v)=d(v)$ であり、道は最短である。到達できない $v$ は $d(v)=+\infty$ のままで、$p(v)$ は未定義である。$\square$

負の閉路を取り出す

判定だけでなく、負の閉路そのものを示せると、不等式の系が矛盾する理由や、儲かる取引の組が分かる。

負の閉路の取り出し

$n-1$ 回のパスのあとに緊張した辺 $(u,v)$ があるとする。これを緩和し、$v$ から $p$ を $n$ 回たどって頂点 $x$ に着く。このとき $p$ は $x$ の先まで定義されていて、$x$ から $p$ をたどると $x$ に戻る。その閉路を逆向きに読んだものは $s$ から到達できる負の閉路である。手間は $O(n)$ である。

$n-1$ 回のパスのあとの値を $D$ とする。緩和のあと $d(v)< D(v)$ である。
$v$ から $p$ をたどる列が頂点の重複なしに未定義の頂点に着いたとする。lem-bf-invariant の (4) より着いた先は $s$ で、$d(s)=0$ である。列は道で、辺は $n-1$ 本以下なので、その重みを $W$ とすると $W\ge d_{n-1}(v)$ である。lem-bf-invariant の (3) を足して $d(v)\ge W$ である。thm-bf-main の (1) と合わせると
$$ d(v)\ge W\ge d_{n-1}(v)\ge D(v)>d(v) $$
となり矛盾する。
よって列は未定義の頂点に着く前に同じ頂点を 2 度通る。列の頂点は $n$ 個以下なので、$n$ 回たどると閉路の上にある。thm-bf-tree の (1) より、この閉路は負の閉路である。閉路の頂点の $d$ は有限なので、lem-bf-invariant の (2) より $s$ から到達できる。$\square$

距離が $-\infty$ の頂点も求まる。

距離が $-\infty$ の頂点

$n-1$ 回のパスのあと緊張している辺の終点の全体を $H$ とする。$\operatorname{dist}(v)=-\infty$ であることと、$v$ が $H$ のどれかの頂点から到達できることは同値である(長さ $0$ の歩道も含める)。よって追加の手間 $O(n+m)$ で求まる。

証明を開く

$\operatorname{dist}(v)$ が有限の頂点の集合を $A$ とする。$v\in A$ なら prop-bf-dist より $\operatorname{dist}(v)=d_{n-1}(v)$ なので、thm-bf-main の (1) と lem-bf-invariant の (2) より $d(v)=\operatorname{dist}(v)$ である。

緊張した辺 $(u,v)$ をとる。$u$ は $s$ から到達でき、$v$ も到達できる。$v\in A$ と仮定する。$\operatorname{dist}(u)=-\infty$ なら $\operatorname{dist}(v)=-\infty$ となるので $u\in A$ であり、$d(v)=\operatorname{dist}(v)\le\operatorname{dist}(u)+w(u,v)=d(u)+w(u,v)$ となって緊張に反する。よって $\operatorname{dist}(v)=-\infty$ である。距離が $-\infty$ の頂点から到達できる頂点の距離も $-\infty$ である。

逆に $\operatorname{dist}(v)=-\infty$ とする。prop-bf-dist の負の閉路 $C$ をとる。$C$ の頂点は $s$ から到達できるので $d$ は有限である。$C$ のどの辺も緊張していなければ、lem-bf-fixed の証明の和より $C$ の重みは $0$ 以上となり、矛盾する。よって $C$ の辺に緊張した辺があり、その終点は $C$ の上にあって $v$ に到達できる。$\square$

差分制約

実数の未知数 $x_v$($v\in V$)についての不等式の系
$$ x_v-x_u\le c(u,v)\qquad((u,v)\in E) $$
を 差分制約 という。作業の開始時刻についての「$v$ の開始は $u$ の開始の $c$ 後より遅くならない」のような条件がこの形である。頂点を未知数、不等式を重み $c$ の辺とみると、最短の道の問題になる。

差分制約の解

$G=(V,E)$ と $c\colon E\to\mathbb{R}$ について次が成り立つ。
(1) 差分制約に解があることと、$G$ に負の閉路がないことは同値である。
(2) 新しい頂点 $q$ と重み $0$ の辺 $q\to v$($v\in V$)を足したグラフで $x_v:=\operatorname{dist}(q,v)$ とおくと、負の閉路がないとき $x$ は解であり、すべての成分が $0$ 以下の解のうちで成分ごとに最大である。
(3) $c$ が整数値なら $x$ も整数値である。
(4) 解を求めるか負の閉路を示す手間は $O(n(n+m))$ である。

不等式を閉路に沿って足す

負の閉路 $v_0\to\dots\to v_l=v_0$ があるとする。解 $x$ があれば、$x_{v_i}-x_{v_{i-1}}\le c(v_{i-1},v_i)$ を足して左辺が $0$ になり、$0\le\sum_ic(v_{i-1},v_i)< 0$ となって矛盾する。
負の閉路がないとする。$q$ に入る辺はないので、足したグラフにも負の閉路はない。すべての頂点は $q$ から到達でき、prop-bf-dist より $x_v$ は有限で、辺 $q\to v$ より $x_v\le0$ である。辺 $(u,v)$ について、$u$ への最短の道に辺をつなぐと $x_v\le x_u+c(u,v)$ であり、$x$ は解である。これで (1) と (2) の前半が示された。
$y$ をすべての成分が $0$ 以下の解とする。$q\to v_1\to\dots\to v_l=v$ を $v$ への最短の道とする。制約を足すと $y_v\le y_{v_1}+\sum_{i\ge2}c(v_{i-1},v_i)\le\sum_{i\ge2}c(v_{i-1},v_i)=x_v$ である。
(3) $x_v$ は整数の和である。(4) 頂点は $n+1$ 個、辺は $n+m$ 本なので、thm-bf-main と thm-bf-cycle による。$\square$

$\varphi(v)=\operatorname{dist}(q,v)$ が辺の重みを $0$ 以上に付け替えることは Dijkstra法 の定理「長さの付け替え」の 2 である。上の定理はそれを不等式の系の言葉で述べたもので、(1) の「解がある」は「付け替えの $\varphi$ がある」と同じことである。

キューを使う変形

値が変わった頂点から出る辺だけを調べれば、無駄な検査が減る。

キューを使う手順

先入れ先出しのキューに $s$ だけを入れて始める。頂点 $u$ を取り出し、$u$ から出る各辺について緊張していれば緩和し、終点がキューになければ入れる。これをキューが空になるまでくり返す。空になったとき $d=\operatorname{dist}$ である。

「緊張した辺の始点はキューの中にあるか、いま調べている頂点である」が保たれる。実際、緊張した辺ができるのは始点の $d$ が下がるときで、そのとき始点はキューに入る。始めは $s$ から出る辺しか緊張しない。空になれば緊張した辺はなく、lem-bf-fixed による。$\square$

頂点を取り出す順を「段」に分けて数えると、負の閉路がなければ $n-1$ 段以内に空になり、手間は $O(nm)$ である(Eri19 §8.7、補題 8.7、p. 293。この記事では証明しない)。負の閉路があれば空にならない(lem-bf-fixed の対偶)ので、段を数えて打ち切る必要がある。

計算の手順

  1. グラフを作る:向きのない辺は両向きに直す。同じ向きの多重辺は重みの最小のものだけ残す。
  2. 初期化する:$d(s)=0$、ほかは $+\infty$ とする。全頂点について負の閉路を調べたいときは、頂点 $q$ と重み $0$ の辺 $q\to v$ を足して $q$ を始点にする(thm-bf-diff)。
  3. パスを行う:全部の辺を順に調べ、緊張していれば緩和する(def-bf-relax)。値が変わらなければ、手順 5 を省いて手順 6 へ進んでよい(lem-bf-fixed)。
  4. $n-1$ 回で打ち切る:$n$ は足した頂点も数える。
  5. 検査する:もう 1 回全部の辺を調べる。緊張した辺がなければ $d$ が距離である(thm-bf-main)。
  6. 結果を読む:緊張した辺がなければ、$p$ を逆にたどって最短の道を得る(thm-bf-tree)。緊張した辺があれば、負の閉路を取り出す(thm-bf-cycle)か、距離が $-\infty$ の頂点を求める(prop-bf-infinity)。

例題

次の図の左が ex-bf-order、右が ex-bf-negative のグラフである。
左:例題のグラフと距離。赤い辺が最短路木。右:負の閉路 a→b→c→a(重み −1)のあるグラフ。a, b, c, d の距離は −∞ で、t の距離は 5。 左:例題のグラフと距離。赤い辺が最短路木。右:負の閉路 a→b→c→a(重み −1)のあるグラフ。a, b, c, d の距離は −∞ で、t の距離は 5。

辺を調べる順で回数が変わる

頂点 $s,a,b,c,d$($n=5$)と辺 $s\to a:4$、$s\to b:5$、$b\to a:-3$、$a\to c:3$、$b\to c:4$、$c\to d:-2$、$c\to a:1$、$d\to b:6$ を考える。閉路は $a\to c\to a$ などで、重みはすべて正である。
使う定理:thm-bf-main、thm-bf-tree。
答え:距離は $a$ が $2$、$b$ が $5$、$c$ が $5$、$d$ が $3$ で、最短路木は $s\to b\to a\to c\to d$ である。

調べる順値の変わるパスの回数1 回目のパスのあとの $(a,b,c,d)$
上に書いた順$1$$(2,5,5,3)$
上の逆の順$4$$(4,5,+\infty,+\infty)$

逆の順の値は $(a,b,c,d)$ の順に $(2,5,7,+\infty)$、$(2,5,5,5)$、$(2,5,5,3)$ と進む。これは $d_2,d_3,d_4$ に等しい。一方、上に書いた順の 1 回目のあとの $c$ の値 $5$ は $d_1(c)=+\infty$ より小さい。手順の値は $d_k$ 以下であるが、等しいとは限らない。

負の閉路の取り出しと $-\infty$

頂点 $s,a,b,c,d,t$($n=6$)と、次の順の辺 $s\to a:1$、$s\to t:5$、$a\to b:2$、$b\to c:-4$、$c\to a:1$、$c\to d:3$ を考える。
使う定理:thm-bf-cycle、prop-bf-infinity。
答え:負の閉路は $a\to b\to c\to a$(重み $-1$)である。距離は $a,b,c,d$ が $-\infty$、$t$ が $5$ である。

パスの回数$a$$b$$c$$d$$t$
1$0$$3$$-1$$2$$5$
2$-1$$2$$-2$$1$$5$
3$-2$$1$$-3$$0$$5$
4$-3$$0$$-4$$-1$$5$
5$-4$$-1$$-5$$-2$$5$
取り出しの計算を開く

5 回のあと、辺 $a\to b$ は $-4+2=-2< -1$ で緊張している。緊張した辺の終点は $b$ だけで、$b$ から到達できる頂点は $a,b,c,d$ である(prop-bf-infinity)。$t$ は含まれない。

緩和すると $p(b)=a$ である。このとき $p(a)=c$、$p(c)=b$ なので、$b$ から $p$ を $6$ 回たどると $b$ に戻る。$b\leftarrow a\leftarrow c\leftarrow b$ を逆向きに読むと、閉路 $b\to c\to a\to b$ が得られ、重みは $-4+1+2=-1$ である。

作業の開始時刻

$x_2-x_1\le3$、$x_3-x_2\le-2$、$x_3-x_1\le2$、$x_1-x_3\le1$、$x_4-x_3\le-1$、$x_4-x_2\le0$ を解く。
使う定理:thm-bf-diff。
答え:$(x_1,x_2,x_3,x_4)=(-1,0,-2,-3)$ が、$0$ 以下の解のうちで最大の解である。全体に定数を足しても解である。ここに $x_2-x_3\le1$ を足すと解はなくなる。$2\to3\to2$ が重み $-2+1=-1$ の負の閉路になるからである。

途中の計算を開く

$q$ から各頂点へ重み $0$ の辺を足し、これらの辺を先に調べ、続けて問題の不等式の順に $1\to2$、$2\to3$、$1\to3$、$3\to1$、$3\to4$、$2\to4$ を調べる。1 回目のパスでは、$q$ からの辺ですべて $0$ になり、$2\to3$ で $x_3=-2$、$3\to1$ で $x_1=-1$、$3\to4$ で $x_4=-3$ となる。ほかの辺は緊張しない。2 回目のパスで値は変わらない。

$x_1=-1$ は $x_1-x_3\le1$ の等号、$x_3=-2$ は $x_3-x_2\le-2$ の等号である。代入すると 6 本の不等式はすべて成り立つ。

掛け算の連鎖の検出

3 種類の通貨 $A,B,C$ の交換レートが、$1$ 単位あたり $A\to B$ が $0.9$、$B\to C$ が $170$、$C\to A$ が $0.0068$、$B\to A$ が $1.1$、$C\to B$ が $0.0058$、$A\to C$ が $150$ であるとする。一周して元より増える交換の連鎖はあるか。
使う考え方:レートの積が $1$ より大きいことと、$-\log$ の和が負であることは同値である。各辺に重み $-\log r$ を付け、thm-bf-main で負の閉路を調べる。
答え:ある。$C\to A\to C$ の積は $0.0068\times150=1.02$ で、$A\to B\to C\to A$ の積は $0.9\times170\times0.0068=1.0404$ である。

途中の計算を開く

重みは $-\log r$ として $A\to B:0.10536$、$B\to C:-5.13580$、$C\to A:4.99083$、$B\to A:-0.09531$、$C\to B:5.14990$、$A\to C:-5.01064$ である(小数 5 桁)。頂点 $q$ と重み $0$ の辺を足して頂点を $4$ 個とし、$q$ の辺のあとは問題に書いた順に調べる。$3$ 回のパスのあとに緊張した辺が残るので負の閉路がある。thm-bf-cycle の手順で取り出すと $C\to A\to C$ が得られ、重みは $-\log1.02\approx-0.01980$ である。

取り出されるのは 1 つの負の閉路であり、重みが最も小さい閉路とは限らない。ここでは $A\to B\to C\to A$ の重み $-\log1.0404\approx-0.03961$ の方が小さい。実際に計算するときは対数の丸め誤差があるので、積が $1$ に近い閉路は積を直接計算して確かめる。

使える条件と反例

外す条件反例成り立たなくなること
到達できる負の閉路がない辺 $s\to a:0$、$a\to b:1$、$b\to a:-2$パスのたびに値が下がり続け、距離が定まらない
パスが $n-1$ 回辺 $s\to a$、$a\to b$、$b\to c$(重み $1$)を後ろから調べる順で $2$ 回$c$ が $+\infty$ のまま
閉路が $s$ から到達できる(検出の範囲)頂点 $s$ と、$s$ から辺のない $a\to b:1$、$b\to a:-2$負の閉路があるのに緊張した辺がない
緩和が狭義辺 $s\to a:0$、$a\to b:0$、$b\to a:0$ を等号でも書き換える直前の頂点のグラフに閉路ができ、木にならない
辺が有向重み $-1$ の向きのない辺 $\{a,b\}$両向きに直すと重み $-2$ の負の閉路になる
表の反例の確かめ

負の閉路:閉路 $a\to b\to a$ の重みは $-1$ である。辺を $s\to a$、$a\to b$、$b\to a$ の順に調べると、$d(a)$ は $k$ 回目のパスのあと $-k$ になり、止まらない。thm-bf-main の (3) のとおりである。
回数:$b\to c$、$a\to b$、$s\to a$ の順に調べると、1 回目のパスのあと $a$ だけ、2 回目で $b$ まで、3 回目で $c$ まで値が入る。$n=4$ で $n-1=3$ 回が必要である。
到達できない閉路:$d(a)=d(b)=+\infty$ のままなので、def-bf-relax の緊張の条件を満たさない。prop-bf-dist のとおり、$s$ からの距離には影響しない。グラフ全体の負の閉路を調べたいときは頂点 $q$ を足す。
狭義の緩和:$d(a)=d(b)=0$ である。辺 $b\to a$ を等号でも書き換えると $p(a)=b$ で、$p(b)=a$ と合わせて閉路になる。重みは $0$ で負ではないので、thm-bf-tree の (1) は成り立たない。$p(a)$ から $s$ に戻れないので、最短の道が読み取れない。狭義なら $p(a)=s$ のままである。
向きのない辺:$a\to b\to a$ の重みは $-2$ である。負の重みの向きのない辺を扱うには別の方法が要る。
負の閉路があるときの最短の道:同じ頂点を通らない道に限っても最小の重みは考えられるが、この記事の手順では求まらない。すべての重みを $-1$ にすると、最小の重みの道は最長の道であり、一般の有向グラフの最長の道は NP 困難である(Eri19 §6.4、p. 235)。Bellman–Ford法が負の閉路を報告して止まるのは手順の欠陥ではない。

よくある誤り

誤り正しくはなぜ
全部の重みに同じ数を足して $0$ 以上にし、Dijkstra法を使う頂点ごとの $\varphi$ で付け替える辺 $s\to t:0$、$s\to a:1$、$a\to t:-2$ に $2$ を足すと、最短の道が $s\to a\to t$ から $s\to t$ に変わる。辺の本数の多い道ほど増える
$k$ 回のパスのあとの $d(v)$ を「辺が $k$ 本以下の最短」と読む辺の本数を制限するなら前のパスの値の写しから計算するex-bf-order。$d(v)\le d_k(v)$ だけが正しい
$n-1$ 回のあとの $d$ を負の閉路があっても距離とする検査で緊張した辺がないことを確かめるex-bf-negative の $a$ の値 $-4$ に意味はない
最後の検査を $d(u)=+\infty$ の辺にも行う$+\infty$ の始点の辺は除く$+\infty$ に負の数を足す実装の誤りで、到達できない辺が緊張して見える
始点から到達できる範囲の判定で全体の負の閉路の有無が分かるとする頂点 $q$ を足すex-bf-counterexamples の到達できない閉路
取り出した閉路を重み最小の閉路とする1 つの負の閉路であるだけであるex-bf-exchange

補足

  • 距離ベクトル経路制御:ネットワークの経路制御の RIP は Bellman–Ford の形の計算に基づき、各ルータが隣から受け取った値で自分の表を更新する(RFC2453 §3.1、§3.4)。通信の切断のあと古い値が互いに参照され、値が少しずつ増えていく現象は counting to infinity とよばれ、RIP では $16$ を無限大とみなして打ち切る(RFC2453 §3.4.1、§3.4.2)。
  • 速い方法:重みが実数の場合、$O(nm)$ を初めて漸近的に改善したのは 2023 年の Fineman の乱択の手順で、手間は高い確率で対数因子を除いて $mn^{8/9}$ である(Fin23 定理 1.1)。重みが $-W$ 以上の整数($W\ge2$)なら、$O(m\log^8n\log W)$ の乱択の手順がある(BNW22)。この記事ではこれらを証明しない。
  • 閉路のないグラフ:閉路がなければ、位相的整列 の順に頂点を見て出る辺を調べると、1 回のパスで終わる。
  • 動的計画法との関係:thm-bf-main の (1) の $d_k$ は 動的計画法 の部分問題である。添字 $k$ を入れて閉路を切るのが動的計画法の見方で、配列を 1 本にする変形で手順が得られる(Eri19 §8.7、pp. 295–296)。

関連項目

参考文献

[1]
Jeremy T. Fineman, Single-Source Shortest Paths with Negative Real Weights in Õ(mn^{8/9}) Time, arXiv:2311.02520, 2023, §1(p. 1)、定理 1.1(p. 1)
[2]
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen, Negative-Weight Single-Source Shortest Paths in Near-linear Time, arXiv:2203.03456, 2022, 要旨(p. 1)
[4]
Jeff Erickson, Algorithms, 1st paperback edition, Independently published, 2019, §6.4(一般の有向グラフの最長の道 p. 235)、§8.7(手順の由来 pp. 289–291、補題 8.6 p. 291、O(VE) の評価 p. 292、Moore の変形と補題 8.7 pp. 292–294、動的計画法としての定式化 pp. 294–296)、§9.4 Johnson の方法(p. 312)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する