Dijkstra法
概要
Dijkstra法（Dijkstra's algorithm）とは、辺の長さがすべて $0$ 以上の重み付き有向グラフで、1 つの頂点 $s$ から各頂点への距離と最短の道を求める手順であり、まだ確定していない頂点のうち暫定値が最小のものを確定し、そこから出る辺で暫定値を書き換えることをくり返す。確定した値は距離に等しく、頂点は距離の小さい順に確定し、直前の頂点をたどると最短路木が得られる。最小の取り出しを二分ヒープで行うと、頂点 $n$ 個・辺 $m$ 本のグラフで $O((n+m)\log n)$ 回の基本操作で終わる。負の長さの辺があると誤ることがあるが、負の閉じた歩道がなければ、頂点に値を割り当てる長さの付け替えで長さを $0$ 以上にしてから使える。
前提知識: 有向グラフ, 重み付きグラフの最短経路, 幅優先探索, Landau記号
辺に $0$ 以上の長さが付いた有向グラフで、1 つの頂点 $s$ から各頂点への最短の道の長さ（距離）を求める手順が Dijkstra 法（Dijkstra's algorithm）である。まだ確定していない頂点のうち暫定の距離が最小のものを確定し、そこから出る辺で暫定の距離を小さく書き換える、という操作をくり返す。無向で連結な場合の手順と正しさは、高校数学の記事 重み付きグラフの最短経路 で地図の例とともに証明している。
この記事では、有向グラフと $s$ から到達できない頂点を含む一般の場合に正しさを証明し（thm-dij-correct）、頂点が距離の小さい順に確定することを示す。次に、最小の頂点を取り出す部分を二分ヒープで実装すると、頂点が $n$ 個・辺が $m$ 本のグラフで $O((n+m)\log n)$ 回の基本操作で終わることを証明する（thm-dij-heap）。最後に、負の長さの辺があると手順が誤ることと、長さが負の閉じた歩道がなければ、頂点に値を割り当てて長さを付け替えることで負の辺を含むグラフにも使えることを証明する（thm-dij-potential）。
定義
この記事のグラフは、頂点の集合 $V$ と、相異なる頂点の順序対 $(u,v)$ の集合 $E$ からなる有限の 有向グラフ $G=(V,E)$ とし、$(u,v)\in E$ を辺 $u\to v$ と書く。$n=\lvert V\rvert$、$m=\lvert E\rvert$ とする。各辺に実数の 長さ $w(u\to v)$ が与えられているとき、$(G,w)$ を重み付き有向グラフという。無向グラフは、各辺 $uv$ を 2 本の辺 $u\to v$、$v\to u$（長さは同じ）に置き換えて有向グラフとみなす。
頂点の列 $P=(x_0,x_1,\dots,x_\ell)$ で各 $x_{i-1}\to x_i$ が辺であるものを $x_0$ から $x_\ell$ への 歩道 といい、その長さを $w(P)=\sum_{i=1}^{\ell}w(x_{i-1}\to x_i)$ と定める（$\ell=0$ なら $0$）。頂点が相異なる歩道を 道 という。
重み付き有向グラフの頂点 $s,v$ について、$s$ から $v$ への歩道の長さの下限を $d(s,v)\in\mathbb{R}\cup\{\pm\infty\}$ と書き、$s$ から $v$ への 距離 という。歩道がなければ $d(s,v)=\infty$ とする。$s$ から $v$ への歩道があるとき、$v$ は $s$ から 到達できる という。
長さがすべて $0$ 以上なら、歩道から閉じた部分（同じ頂点の 2 回の出現の間）を除いても長さは増えないので、どの歩道もそれ以下の長さの道を含む。道は有限個なので、到達できる $v$ について $d(s,v)$ は道の長さの最小値として実現され、$d(s,s)=0$ である。さらに、辺 $u\to v$ について
$$
d(s,v)\le d(s,u)+w(u\to v)
$$
が成り立つ（$s$ から $u$ への最短の道に辺 $u\to v$ をつなげばよい。$d(s,u)=\infty$ なら右辺は $\infty$）。
長さがすべて $0$ 以上の重み付き有向グラフ $(G,w)$ と頂点 $s$ に対し、次の手順を Dijkstra 法 という。各頂点 $v$ に 暫定値 $D(v)\in\mathbb{R}\cup\{\infty\}$ を記録し、$D(v)$ を書き換えたときは 直前の頂点 $p(v)$ も記録する。確定した頂点 の集合を $S$ とする。
- $D(s):=0$、$v\ne s$ について $D(v):=\infty$、$S:=\emptyset$ とする。
- $V\setminus S$ の頂点で暫定値が有限のものがなければ終わる。あれば、そのうち $D(u)$ が最小のもの $u$ を 1 つ選び、$S:=S\cup\{u\}$ とする（$u$ を 確定する）。
- $u$ から出る各辺 $u\to v$ で $v\notin S$ のものについて、$D(u)+w(u\to v)< D(v)$ なら $D(v):=D(u)+w(u\to v)$、$p(v):=u$ とする。2 に戻る。
手順 2 を行うたびに $S$ が 1 つ増えるので、手順は高々 $n$ 回のくり返しで終わる。辺の長さがすべて $1$ なら、確定する順は 幅優先探索 で頂点を調べる順と同じく距離の順になり（thm-dij-correct の 3）、暫定値は距離と一致する。
頂点 $s,a,b,c,t,z$ と辺
$$
s\xrightarrow{4}a,\quad s\xrightarrow{1}b,\quad b\xrightarrow{2}a,\quad a\xrightarrow{1}c,\quad b\xrightarrow{5}c,\quad c\xrightarrow{3}t,\quad a\xrightarrow{6}t,\quad t\xrightarrow{1}b,\quad z\xrightarrow{2}s
$$
（矢印の上の数が長さ）のグラフで Dijkstra 法を行う。各回の手順 3 の後の暫定値は次のとおりである（確定した頂点の値を太字にし、以後は空ける）。
| 回 | 確定する頂点 | $s$ | $a$ | $b$ | $c$ | $t$ | $z$ |
|---|---|---|---|---|---|---|---|
| 1 | $s$ | $\boldsymbol{0}$ | $4$ | $1$ | $\infty$ | $\infty$ | $\infty$ |
| 2 | $b$ | $3$ | $\boldsymbol{1}$ | $6$ | $\infty$ | $\infty$ | |
| 3 | $a$ | $\boldsymbol{3}$ | $4$ | $9$ | $\infty$ | ||
| 4 | $c$ | $\boldsymbol{4}$ | $7$ | $\infty$ | |||
| 5 | $t$ | $\boldsymbol{7}$ | $\infty$ |
5 回目に $t$ を確定すると、辺 $t\to b$ の先の $b$ はすでに確定しているので何もしない。残る $z$ の暫定値は $\infty$ なので手順は終わる。$z$ へ入る辺はないので $z$ は $s$ から到達できず、$d(s,z)=\infty$ である。確定した値は $0,1,3,4,7$ と小さい順に並ぶ。$t$ から直前の頂点をたどると $t\leftarrow c\leftarrow a\leftarrow b\leftarrow s$ で、道 $s\to b\to a\to c\to t$ の長さは $1+2+1+3=7$ である。$t$ へのほかの道 $s\to a\to t$（$10$）、$s\to b\to a\to t$（$9$）、$s\to b\to c\to t$（$9$）、$s\to a\to c\to t$（$8$）はどれも長い。
主定理：Dijkstra 法は正しい
長さがすべて $0$ 以上の重み付き有向グラフ $(G,w)$ と頂点 $s$ に Dijkstra 法を行う。終わったとき次が成り立つ。
- $S$ は $s$ から到達できる頂点の全体であり、すべての頂点 $v$ について $D(v)=d(s,v)$ である。
- $v\in S\setminus\{s\}$ から直前の頂点を $v,\ p(v),\ p(p(v)),\ \dots$ とたどると $s$ に着き、その逆順は $s$ から $v$ への長さ $d(s,v)$ の道である。辺 $p(v)\to v$（$v\in S\setminus\{s\}$）の全体は、$s$ から $S$ の各頂点への道がただ 1 つずつある部分グラフ（$s$ を根とする 最短路木）をなす。
- 確定した順に頂点を $u_1=s,u_2,\dots,u_r$ とすると、$d(s,u_1)\le d(s,u_2)\le\dots\le d(s,u_r)$ である。
証明は、手順の各段階で次の 2 つの性質が保たれることによる。
- (I1) $z\in S$ なら $D(z)=d(s,z)$ で、$D(z)$ と $p(z)$ はその後変わらない。
- (I2) $S\ne\emptyset$ なら $s\in S$ で、$v\notin S$ について $D(v)=\min\{D(z)+w(z\to v): z\in S,\ z\to v\in E\}$（該当する $z$ がなければ $\infty$）であり、$D(v)< \infty$ なら $p(v)$ は最小を与える $z$ の 1 つである。
（最初の確定）$S=\emptyset$ のとき暫定値が有限なのは $D(s)=0$ だけなので、最初に確定するのは $s$ で、$D(s)=0=d(s,s)$ である。$s$ を加えた後に (I1)(I2) が成り立つことは、下の「性質が保たれること」と同じ議論で分かる（$S=\emptyset$ のとき $v\ne s$ の暫定値は $\infty$ で、空集合の最小に等しい）。
（確定の一歩）$S\ne\emptyset$ で (I1)(I2) が成り立つとし、手順 2 で $u\notin S$（$D(u)< \infty$）を確定するとする。$D(u)=d(s,u)$ を示す。(I2) により $D(u)=D(z)+w(z\to u)=d(s,z)+w(z\to u)$ となる $z\in S$ があり、距離の不等式により $D(u)\ge d(s,u)$ である。逆に、$s$ から $u$ への任意の歩道 $P$ をとる。$s\in S$、$u\notin S$ なので、$P$ の上で初めて $S$ の外へ出る辺 $y'\to y$（$y'\in S$、$y\notin S$）がある。$P$ の $y'$ までの部分の長さは $d(s,y')=D(y')$ 以上なので、(I2) と $u$ の選び方から
$$
w(P)\ \ge\ D(y')+w(y'\to y)+\underbrace{(\text{$P$ の $y$ から先の長さ})}_{\ge0}\ \ge\ D(y)\ \ge\ D(u)
$$
である。$P$ は任意なので $d(s,u)\ge D(u)$、よって $D(u)=d(s,u)$ である。
（性質が保たれること）手順 3 で書き換えるのは $S$ の外の頂点だけなので、$u$ を加えた後も (I1) が成り立つ。$v\notin S\cup\{u\}$ について、(I2) の最小をとる集合に加わるのは $z=u$ の項だけで、手順 3 はまさに $D(v)$ を $\min\{D(v),D(u)+w(u\to v)\}$ に置き換え、真に小さくなったときだけ $p(v):=u$ とする。よって (I2) も保たれる。
（1 の証明）上により確定した頂点 $z$ では $D(z)=d(s,z)< \infty$ なので、$S$ の頂点は到達できる。到達できる $v\notin S$ があるとすると、$s$ から $v$ への歩道で初めて $S$ の外へ出る辺 $y'\to y$ について、(I2) により $D(y)\le D(y')+w(y'\to y)< \infty$ となり、手順が終わる条件に反する。よって $S$ は到達できる頂点の全体で、$S$ の外の頂点では $D(v)=\infty=d(s,v)$ である（(I2) の最小は空）。
（2 の証明）$v\in S\setminus\{s\}$ について、(I2) により $D(v)< \infty$ となった時点の $p(v)$ は $S$ に属し、(I1) により $v$ を確定した後は変わらないので、$p(v)$ は $v$ より前に確定し、$d(s,v)=d(s,p(v))+w(p(v)\to v)$ である。たどるたびに確定の順が前に戻るので、有限回で $p$ の記録のない確定した頂点に着く。$s$ は最初に確定し、それより前に書き換えられないので、それは $s$ である。等式を足し合わせると、逆順の道の長さは $d(s,v)$ になる。各 $v\in S\setminus\{s\}$ に入る辺 $p(v)\to v$ はちょうど 1 本で、たどると必ず $s$ に着くので、$s$ から $v$ への道はこの辺の集まりの中にただ 1 つある。
（3 の証明）$u_k$ を確定する時点で、$S$ の外のすべての $x$ について $D(x)\ge D(u_k)$ である。その手順 3 で書き換えた値は $D(u_k)+w\ge D(u_k)$ なので、次に確定する $u_{k+1}$ について $D(u_{k+1})\ge D(u_k)$ となる。1 により $D(u_k)=d(s,u_k)$ である。$\square$
証明で長さが $0$ 以上であることを使ったのは、最初の確定で $d(s,s)=0$ としたところ、「確定の一歩」で $P$ の $y$ から先の長さを $0$ 以上としたところと、3 の証明の $w\ge0$ である。重み付きグラフの最短経路 の証明は、確定する順の帰納法で同じ不等式を使っている。
実数 $c_1,\dots,c_r\ge0$ に対し、頂点 $s,v_1,\dots,v_r$ と辺 $s\to v_i$（長さ $c_i$）だけからなるグラフで Dijkstra 法を行うと、$v_1,\dots,v_r$ は $c_i$ の小さい順に確定する。
$d(s,v_i)=c_i$ なので、thm-dij-correct の 3 による。$\square$
したがって Dijkstra 法のどの実装も、$r$ 個の数を並べ替える手順を含む。
計算の手間
優先度付きキュー
手間は、各頂点から出る辺の一覧（隣接リスト）が与えられ、長さの足し算と比較を 1 回の基本操作と数えて測る。手順 2 の「暫定値が有限で最小の頂点を取り出す」部分を、次の操作をもつ 優先度付きキュー に任せる。キューには「$S$ の外で暫定値が有限の頂点」を、暫定値をキーとして入れておく。
- 挿入：頂点をキーとともに加える。
- 最小の取り出し：キーが最小の頂点を 1 つ除いて返す。
- キーの減少：キューの中の頂点のキーを小さい値に変える。
Dijkstra 法を優先度付きキューで行うと、挿入と最小の取り出しはそれぞれ $n$ 回以下、キーの減少は $m$ 回以下であり、手順 3 で調べる辺は合わせて $m$ 本以下である。
各頂点は高々 1 回確定し、確定するときにだけ最小の取り出しを受けるので、取り出しは $n$ 回以下である。手順 3 で調べるのは確定した頂点から出る辺なので、各辺は高々 1 回調べられる。頂点は暫定値が $\infty$ から有限になるときに挿入され、有限の暫定値は $\infty$ に戻らないので、挿入は各頂点で高々 1 回である。キーの減少は手順 3 で辺を 1 本調べて書き換えるときに高々 1 回起こるので、$m$ 回以下である。$\square$
キューを頂点で番号付けた配列（暫定値を書き込むだけ）で表すと、挿入とキーの減少は $O(1)$、最小の取り出しは全体をなめて $O(n)$ なので、全体は $O(n^2+m)=O(n^2)$ である（$m\le n(n-1)$）。
二分ヒープ
二分ヒープ とは、$k$ 個の頂点を配列 $H[1],\dots,H[k]$ に並べたもので、$2\le i\le k$ について $H[\lfloor i/2\rfloor]$ のキーが $H[i]$ のキー以下であるもの（ヒープ条件）をいう。$\lfloor i/2\rfloor$ を $i$ の 親、$2i,2i+1$（$k$ 以下のもの）を 子 と呼ぶ（二分木 の位置の番号付け）。各頂点がどの位置にあるかも別の配列に記録する。ヒープ条件から、キーが最小の頂点は $H[1]$ にある（親をたどると $1$ に着き、キーは親へ進むたびに増えない）。
- 上げる（位置 $i$）：$i\ge2$ で $H[i]$ のキーが親のキーより小さい間、$H[i]$ と親を入れ替えて $i:=\lfloor i/2\rfloor$ とする。
- 下げる（位置 $i$）：子のうちキーが最小のものを $j$ とし、$H[j]$ のキーが $H[i]$ のキーより小さい間、入れ替えて $i:=j$ とする。
挿入は $H[k+1]$ に置いて上げる。キーの減少はキーを変えてその位置で上げる。最小の取り出しは $H[1]$ を返し、$H[k]$ を $H[1]$ に移して $k:=k-1$ とし、位置 $1$ で下げる。
$k$ 個の頂点の二分ヒープで、挿入・最小の取り出し・キーの減少はヒープ条件を保ち、それぞれ $O(\log k)$ 回の基本操作で終わる。
（手間）位置 $i$ から親を $j$ 回たどると $\lfloor i/2^j\rfloor$ になるので、上げる・下げるの入れ替えは $\lfloor\log_2 k\rfloor$ 回以下で、1 回の入れ替えは定数回の比較と書き込みである。
（条件が保たれること）要点：入れ替えのたびに、条件の崩れうる箇所が 1 つの位置とその親（または子）の間だけに限られ、その箇所が根（または葉）へ動く。
詳しい証明を開く
上げる場合：「ヒープ条件が成り立たないのは $i$ とその親の組だけで、$i$ に親と子の両方があれば、親のキーは $i$ の子のキー以下」という性質 (U) を考える。末尾に置いた直後は $i$ に子がなく、キーを減らした直後は、減らす前の $H[i]$ のキーが親のキー以上かつ子のキー以下だったので、(U) が成り立つ。$H[i]$ のキー $a$ が親 $q$ のキー $b$ より小さくて入れ替えると、位置 $i$ には $b$ が来て、$i$ の子のキーは (U) により $b$ 以上である。位置 $q$ には $a$ が来て、$q$ のもう一方の子のキーは $b$ 以上（その組ではヒープ条件が成り立っていた）なので $a$ より大きく、$a< b$ である。崩れうるのは $q$ とその親の組だけで、$q$ の親のキーは $b$ 以下（元のヒープ条件）なので $q$ の 2 つの子のキー以下であり、(U) が位置 $q$ で成り立つ。キーが親以上になるか $i=1$ になれば、ヒープ条件が全体で成り立つ。
下げる場合：成り立たないのは位置 $i$ とその子の組だけで、$i$ の親のキーは $i$ の子のキー以下とする（取り出しの直後の $i=1$ はこの形）。子のうち最小の $j$ と入れ替えると、位置 $i$ には $H[j]$ が来て、これは $i$ のもう一方の子以下で、$i$ の親のキー以上である（仮定）。崩れうるのは $j$ とその子の組だけで、$j$ の親 $i$ の新しいキーは元の $H[j]$ で、$j$ の子のキー以下（元のヒープ条件）なので性質が保たれる。$H[i]$ が子の最小以下になれば、または子がなくなれば、全体で成り立つ。$\square$
長さがすべて $0$ 以上の重み付き有向グラフで、優先度付きキューを二分ヒープで実装した Dijkstra 法は $O((n+m)\log n)$ 回の基本操作で終わる。
キューの頂点は $n$ 個以下なので、lem-dij-heap により各操作は $O(\log n)$ 回の基本操作で終わる。prop-dij-count により操作は $2n+m$ 回以下で、手順 3 で辺を調べる手間は合わせて $O(m)$ なので、全体は $O((n+m)\log n)$ である。$\square$
辺の少ない（$m$ が $n$ に比例する程度の）グラフでは、二分ヒープの $O(n\log n)$ が配列の $O(n^2)$ より速い。逆に $m$ が $n^2$ に比例するグラフでは配列のほうが速い。Fibonacci ヒープを使うと $O(m+n\log n)$ になることが知られている（Eri19 §8.6、p. 288。この記事では証明しない）。cor-dij-sort により、確定の順を出力するどの実装も $r$ 個の数の並べ替えを行っている。
負の長さの辺
辺 $s\xrightarrow{2}a$、$s\xrightarrow{4}b$、$b\xrightarrow{-3}a$ のグラフで手順を行うと、1 回目に $s$ を確定して $D(a)=2$、$D(b)=4$ とし、2 回目に $a$ を $2$ で確定する。3 回目に $b$ を確定するが、$a$ はもう確定しているので辺 $b\to a$ では書き換えない。ところが道 $s\to b\to a$ の長さは $4-3=1$ で、$d(s,a)=1< 2$ である。prf-dij-correct の「確定の一歩」で、$a$ への歩道 $s\to b\to a$ の $b$ から先の長さが $-3< 0$ になり、不等式が崩れる。
すべての辺に同じ数を足して長さを $0$ 以上にしても、最短の道は保たれない。辺の本数の多い道ほど多く足されるからである。
辺 $s\xrightarrow{1}t$、$s\xrightarrow{2}x$、$x\xrightarrow{-2}t$ のグラフでは、$s$ から $t$ への道は $s\to t$（長さ $1$）と $s\to x\to t$（長さ $0$）で、後者が最短である。すべての辺に $2$ を足すと長さは $3$ と $4$ になり、前者が最短になる。
頂点ごとに値を割り当てる付け替えなら、すべての歩道の長さが両端だけで決まる量ずれるので、最短の道は保たれる（Eri19 §9.3–9.4、pp. 311–312）。
$(G,w)$ を重み付き有向グラフ（長さは負でもよい）とし、関数 $\varphi:V\to\mathbb{R}$ に対して $w_\varphi(u\to v):=w(u\to v)+\varphi(u)-\varphi(v)$ とおく。
- $x$ から $y$ への任意の歩道 $P$ について $w_\varphi(P)=w(P)+\varphi(x)-\varphi(y)$ である。とくに $w$ と $w_\varphi$ で、$x$ から $y$ への最短の歩道は同じで、$d_\varphi(x,y)=d(x,y)+\varphi(x)-\varphi(y)$ である（$d_\varphi$ は $w_\varphi$ に関する距離）。
- すべての辺で $w_\varphi\ge0$ となる $\varphi$ が存在することと、$G$ に長さ（$w$ に関する）が負の閉じた歩道がないことは同値である。
- $w_\varphi\ge0$ なら、$w_\varphi$ で Dijkstra 法を行い、終わったときの値から $d(s,v)=D(v)-\varphi(s)+\varphi(v)$ として距離が求まる（到達できない $v$ では $\infty$）。
1：$P=(x_0,\dots,x_\ell)$ について $w_\varphi(P)=\sum_i\bigl(w(x_{i-1}\to x_i)+\varphi(x_{i-1})-\varphi(x_i)\bigr)$ で、$\varphi$ の項は途中の頂点で打ち消し合い $\varphi(x_0)-\varphi(x_\ell)$ が残る。$x$ から $y$ への歩道はどれも同じ量 $\varphi(x)-\varphi(y)$ だけ長さが変わるので、後半が従う。
2：$w_\varphi\ge0$ なら、閉じた歩道 $C$（$x=y$）について 1 により $w(C)=w_\varphi(C)\ge0$ である。逆に負の閉じた歩道がないとする。新しい頂点 $q$ と、長さ $0$ の辺 $q\to v$（$v\in V$）を加えたグラフを考える。$q$ に入る辺はないので、負の閉じた歩道は増えない。歩道から閉じた部分を除いても長さは増えないので、$q$ から $v$ への距離 $\varphi(v):=d(q,v)$ は有限個の道の長さの最小値で、辺 $q\to v$ により $\varphi(v)\le0$ である。辺 $u\to v$ について、最短の道に辺をつなげば $\varphi(v)\le\varphi(u)+w(u\to v)$、すなわち $w_\varphi(u\to v)\ge0$ である。
3：thm-dij-correct により $D(v)=d_\varphi(s,v)$ で、1 から従う。$\square$
2 の $\varphi$ は、負の辺を許す Bellman–Ford 法で $O(nm)$ の手間で求まる（Eri19 §9.4、p. 312。この記事では証明しない）。すべての頂点の組の距離を求めるときは、$\varphi$ を 1 回求め、各頂点から $w_\varphi$ で Dijkstra 法を行えばよい（Johnson の方法）。ex-dij-negative では $\varphi(s)=0$、$\varphi(a)=-3$、$\varphi(b)=0$ とすると $w_\varphi(s\to a)=5$、$w_\varphi(s\to b)=4$、$w_\varphi(b\to a)=0$ がすべて $0$ 以上になり、$w_\varphi$ での Dijkstra 法は $d_\varphi(s,a)=4$ を与え、$d(s,a)=4-0+(-3)=1$ が正しく求まる。
例と反例
thm-dij-correct の仮定と手順のうち 1 つを外すと、次のように崩れる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 辺の長さが $0$ 以上 | ex-dij-negative | 確定した値が距離に等しいこと（$a$ を $2$ で確定するが $d(s,a)=1$） |
| 手順 2 で暫定値が最小の頂点を確定する | ex-dij-run の 2 回目に、最小の $b$（$1$）でなく $a$（$4$）を確定する | 確定した値が距離に等しいこと（$a$ を $4$ で確定するが $d(s,a)=3$） |
| 付け替えで $w_\varphi\ge0$ となる（thm-dij-potential の 3） | ex-dij-negative で $\varphi=0$（$w_\varphi=w$） | 付け替えた長さで求めた値が距離に等しいこと |
ex-dij-negative のグラフには負の閉じた歩道がないので、距離はきちんと定まっている。崩れるのは手順のほうである。一方、負の閉じた歩道があると、それを何度も回る歩道の長さはいくらでも小さくなり、$s$ からその閉じた歩道を経て行ける頂点 $v$ では $d(s,v)=-\infty$ になる（重み付きグラフの最短経路 の反例「いくらでも短い道がある」）。
関連項目
- 前提: 有向グラフ, 幅優先探索, Landau記号
- 高校数学: 重み付きグラフの最短経路
- 比較: 全域木, 距離(グラフ)
- 応用: 巡回セールスマン問題, 組合せ最適化
- 発展: 計算量理論, 二分木
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
