Bellman–Ford法(Bellman–Ford algorithm)とは、辺の重みが負でもよい有向グラフで、1 つの頂点から各頂点への距離を求める手順であり、すべての辺を順に調べて暫定の値を下げることを、頂点の数より 1 回少ない回数だけくり返す。手間は頂点の数と辺の数の積に比例する。そのあとに値を下げられる辺が残ることと、始点から到達できる負の閉路があることは同値で、記録した直前の頂点をたどると最短路木や負の閉路が得られる。負の辺のある最短の道、差分制約の不等式の解法、付け替えの重みの計算、一周して増える交換の検出に使う。
Bellman–Ford法(Bellman–Ford algorithm)は、辺の重みが負でもよい有向グラフで、1 つの頂点から各頂点への最短の歩道の重みを求める手順である。すべての辺を順に調べて暫定の値を下げることを、頂点の個数より 1 回少ない回数だけくり返す。
Dijkstra法 は、暫定値が最小の頂点を確定していく手順で、確定が正しいのは辺の長さが $0$ 以上だからである。負の辺があると、確定した頂点にあとからもっと短い歩道が見つかることがある(Dijkstra法 の節「負の長さの辺」)。Bellman–Ford法は確定をやめる。どの頂点の値も、最後まで書き換えてよい暫定値のままにしておき、全部の辺を調べ直す。遅くなる代わりに、負の辺があっても正しく、さらに、距離が定まらない原因である負の閉路を見つけられる。
この記事で計算すること・証明することは次のとおりである。
$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)〜(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$)。
辺を調べる順は任意とする。
(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)$ である。
パスの回数の $n-1$ は減らせない。最短の道の辺を後ろから順に調べる順では、1 回のパスで 1 頂点しか進まない(ex-bf-counterexamples)。逆に、最短路木の辺を根に近い順に先に調べる順なら 1 回で済む(ex-bf-order)。
$p$ を、辺 $p(v)\to v$ の集まり($p(v)$ が定義された $v$ 全体)とみる。これを 直前の頂点のグラフ という。
判定だけでなく、負の閉路そのものを示せると、不等式の系が矛盾する理由や、儲かる取引の組が分かる。
$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$ の頂点も求まる。
$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 の対偶)ので、段を数えて打ち切る必要がある。
次の図の左が ex-bf-order、右が ex-bf-negative のグラフである。
左:例題のグラフと距離。赤い辺が最短路木。右:負の閉路 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$ 以下であるが、等しいとは限らない。
頂点 $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 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する