グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する

0. この記事の要点

道路地図で「目的地まで何回曲がれば着くか」「何分で着くか」を調べるとき、地図を点と線のつながりだけに単純化したものがグラフです。この記事では、そのグラフの上を手際よく調べて回る 3 つの方法（幅優先探索・深さ優先探索・ダイクストラ法）を取り上げ、なぜ正しい答えが出るのかを小さな例で手を動かしながら確かめます。読み終えると、最短経路や依存関係の順序づけの問題を、かかる時間まで含めて説明できるようになります。

• グラフの表現は隣接行列（辺の有無を表にしたもの）と隣接リスト（頂点ごとに隣の頂点を並べたもの）の 2 つが基本です。領域は $\Theta(|V|^2)$ と $\Theta(|V|+|E|)$、辺の有無の判定は $O(1)$ と $O(\deg u)$ で、得意なことが正反対です。
• 幅優先探索（BFS）は、始点からの辺の本数が最小の経路を、$O(|V|+|E|)$ 時間で全頂点について同時に求めます。正しさの核は「キューの中の距離はほぼ揃っている」という単調性です。
• 深さ優先探索（DFS）は、頂点の発見時刻と完了時刻が入れ子になるという構造を作ります。この構造から、有向閉路の検出とトポロジカルソートが同じ $O(|V|+|E|)$ で得られます。
• ダイクストラ法は、辺の重みがすべて非負という仮定の下で、重み付き最短経路を求めます。非負性は「まだ確定していない頂点を経由しても近道にならない」ことを保証するために必須で、これを外すと反例が作れます。
• 二分ヒープ（最小の値をすぐ取り出せる木構造）を優先度付きキュー（最小の値から先に取り出せる入れ物）に使うと、ダイクストラ法は $O(|V| + |E|\log|V|)$ 時間で動きます。連結グラフでは $O(|E|\log|V|)$ と書けます。密グラフでは配列による $O(|V|^2)$ 実装のほうが速くなります。

この記事で使う事前知識

• O 記法・Θ 記法: 入力が大きくなるときに、実行時間がどの速さで増えるかを表す書き方。$\Theta$ は上からも下からも同じ速さで抑えられることを表します。→ O 記法
• キュー: 先に入れたものから先に取り出す入れ物（先入れ先出し）。幅優先探索で使います。→ キュー
• スタック: 後に入れたものから先に取り出す入れ物（後入れ先出し）。深さ優先探索の再帰呼び出しはこれと同じ動きをします。→ スタック
• 二分探索: 並んだ配列の真ん中と比べて、探す範囲を半分ずつに絞る探索。→ 探索アルゴリズム
• 数学的帰納法: 最初の場合が成り立ち、「ある場合が成り立てば次の場合も成り立つ」と言えれば、すべての場合が成り立つという証明の型。この記事の証明で何度も使います。

1. 動機：つながり方だけを取り出す

1736 年、オイラーはケーニヒスベルクの町を流れる川に架かる 7 本の橋を、すべて 1 回ずつ渡って出発点に戻れるか、という問題を考えました。彼がやったことは、町の地図から距離も形も捨て、陸地を点、橋を線に置き換えることでした。残るのは「どことどこがつながっているか」だけです。この抽象化がグラフの始まりです。

同じ抽象化が現代の計算のいたるところに現れます。カーナビは交差点を頂点、道路を辺、所要時間を重みとするグラフの最短経路を解いています。パッケージマネージャは、パッケージを頂点、依存関係を有向辺とするグラフに循環がないかを調べ、インストール順序を決めます。表面上まったく違うこれらの問題が、到達可能か・最少の辺数で到達するには・総コストが最小の経路は何かという数個の問いに帰着します。

グラフでは計算量の測り方が一段複雑になります。ソートの入力サイズは配列の長さ $n$ ひとつでした（ソートアルゴリズム の ソート問題（定義 2.1）［ソートアルゴリズム］）。グラフの入力サイズは頂点数 $|V|$ と辺数 $|E|$ の2 つで決まり、しかも $|E|$ は $|V|-1$（木）から $|V|(|V|-1)/2$（完全グラフ）まで大きく動きます。そのため「$O(|V|^2)$ と $O(|E|\log|V|)$ のどちらが速いか」は入力の性質を指定しないと決まりません。計算量とO記法 の O 記法（定義 3.1）［計算量と O 記法］ による漸近評価が実際に効いてくる場面です。

この章では、グラフの表現を決めたうえで、BFS・DFS・ダイクストラ法を動く実装と証明の形で押さえます。

ノート

以下、$O(|V|+|E|)$ を $O(V+E)$ と略記することがあります。絶対値記号が省略されているだけで、慣習的な書き方です。

2. 準備：グラフの定義と 2 つの表現

2.1. グラフ・道・距離

定義 2.1（グラフ）↗

$V$ を有限集合とする。

無向グラフとは、対 $G=(V,E)$ であって $E \subseteq \{\, \{u,v\} \mid u,v \in V,\ u \ne v \,\}$ を満たすものをいう。$V$ の元を頂点、$E$ の元を辺という。

有向グラフとは、対 $G=(V,E)$ であって $E \subseteq V \times V$ を満たすものをいう。$(u,v)\in E$ を $u$ から $v$ への有向辺という。

無向グラフの頂点 $u$ の次数 $\deg(u)$ を、$u$ を含む辺の個数とする。有向グラフでは、$u$ を始点とする辺の個数を出次数 $\deg^{+}(u)$、$u$ を終点とする辺の個数を入次数 $\deg^{-}(u)$ とする。

さらに写像 $w : E \to \mathbb{R}$ が与えられているとき、$(G,w)$ を重み付きグラフといい、$w(e)$ を辺 $e$ の重みという。

この定義は多重辺（同じ 2 頂点を結ぶ 2 本以上の辺）と無向の自己ループを許していません。このようなグラフを単純グラフといいます。有向グラフでは $(u,u)\in E$ を許すことにします。

定義 2.2（歩道・道・距離）↗

グラフ $G=(V,E)$ において、頂点の列 $W=(v_0,v_1,\ldots,v_k)$ が、すべての $i$ について $v_i$ と $v_{i+1}$ が辺で結ばれている（有向グラフなら $(v_i,v_{i+1}) \in E$）とき、$W$ を $v_0$ から $v_k$ への歩道といい、$k$ をその長さという。

歩道 $W$ の頂点がすべて相異なるとき、$W$ を道という。$k \ge 1$ で、$v_0=v_k$ かつ $v_0,\ldots,v_{k-1}$ が相異なるとき、$W$ を閉路という。ただし無向グラフでは、同じ辺を往復するだけの $k=2$ の場合を除くため $k\ge3$ を要求する。

$s$ から $v$ への歩道が存在するとき、$v$ は $s$ から到達可能であるという。$s$ から $v$ への歩道の長さの最小値を $\delta(s,v)$ と書き、$s$ から $v$ への距離という。到達可能でないときは $\delta(s,v)=\infty$ と定める。

歩道は同じ頂点を何度通ってもよい辿り方、道は同じ頂点を 2 度通らない辿り方です。距離を「歩道の長さの最小値」で定義しましたが、最小を与える歩道は必ず道になります。実際、歩道の中に同じ頂点 $x$ が 2 回現れれば、その間の部分（長さ 1 以上）を切り取ってより短い歩道が作れるので、最小性に反するからです。

以下、この章を通じて次の無向グラフを使います。

この章で使う無向グラフ G0。頂点は 6 個、辺は 7 本。

2.2. 隣接行列と隣接リスト

定義 2.3（隣接行列と隣接リスト）↗

$V=\{v_1,\ldots,v_n\}$ と番号付けされたグラフ $G=(V,E)$ に対し、$n \times n$ 行列 $A$ を

$$A_{ij} = \begin{cases} 1 & (v_i \text{ と } v_j \text{ が辺で結ばれている、有向グラフなら } (v_i,v_j) \in E) \\ 0 & (\text{そうでない}) \end{cases}$$

で定め、$G$ の隣接行列という。重み付きグラフでは $1$ の代わりに重み $w$ を置き、辺がないところには $\infty$ を置く。

各頂点 $u$ に対し、$u$ に隣接する頂点（有向グラフでは $u$ を始点とする辺の終点）を並べたリスト $\mathrm{Adj}[u]$ の組を、$G$ の隣接リストという。

例 2.4（G0 の 2 つの表現）

上のグラフ $G_0$ を、頂点の順序を $s,a,b,c,d,e$ として表します。隣接行列は

$$A = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{pmatrix}$$

です。無向グラフなので $A$ は対称行列になります。$36$ 個の成分のうち $1$ は $14$ 個で、辺の本数 $7$ のちょうど 2 倍です。

隣接リストは次のとおりです。

頂点	隣接頂点	次数
$s$	$a,\ b$	2
$a$	$s,\ c$	2
$b$	$s,\ c,\ d$	3
$c$	$a,\ b,\ e$	3
$d$	$b,\ e$	2
$e$	$c,\ d$	2

次数の総和は $2+2+3+3+2+2=14=2\times 7$ です。この一致は偶然ではありません。

補題 2.5（握手補題）✓

無向単純グラフ $G=(V,E)$ について

$$\sum_{u \in V} \deg(u) = 2|E|$$

が成り立つ。有向グラフ $G=(V,E)$ については

$$\sum_{u \in V} \deg^{+}(u) = \sum_{u \in V} \deg^{-}(u) = |E|$$

が成り立つ。

証明（補題 2.5）

無向の場合、集合 $S = \{\,(u,e) \mid u \in V,\ e \in E,\ u \in e \,\}$ の元の個数を 2 通りに数えます。

頂点 $u$ を固定して数えると、$u$ を含む辺は定義により $\deg(u)$ 本なので、$u$ に対応する組は $\deg(u)$ 個です。$u$ について足し上げて $|S| = \sum_{u} \deg(u)$ を得ます。

辺 $e=\{u,v\}$ を固定して数えると、単純グラフでは $u \ne v$ なので、$e$ を含む組は $(u,e)$ と $(v,e)$ のちょうど 2 個です。$e$ について足し上げて $|S| = 2|E|$ を得ます。両者を等しいと置けば主張が従います。

有向の場合、各辺 $(u,v)$ は始点 $u$ の出次数に 1 だけ、終点 $v$ の入次数に 1 だけ寄与し、逆に出次数・入次数への寄与はすべてこの形なので、どちらの総和も辺の総数 $|E|$ に等しくなります。

∎

命題 2.6（2 つの表現の計算量）✓

$G=(V,E)$ を頂点数 $n=|V|$、辺数 $m=|E|$ のグラフとする。

(a) 隣接行列表現は $\Theta(n^2)$ 語の記憶領域を使う。与えられた $u,v$ について辺の有無の判定は $O(1)$ 時間、$u$ に隣接するすべての頂点の列挙は $\Theta(n)$ 時間、すべての辺の走査は $\Theta(n^2)$ 時間で行える（かつ、それより速くはできない）。

(b) 隣接リスト表現は $\Theta(n+m)$ 語の記憶領域を使う。$u$ に隣接するすべての頂点の列挙は $\Theta(1+\deg u)$ 時間、すべての辺の走査は $\Theta(n+m)$ 時間で行える。一方、与えられた $u,v$ について辺の有無の判定は、最悪 $\Theta(\deg u)$ 時間かかる。

証明（命題 2.6）

(a) 行列は $n^2$ 個の成分を持つので領域は $\Theta(n^2)$ です。辺の有無は $A_{ij}$ という 1 回の添字アクセスで読めるので $O(1)$ です。$u$ の隣接頂点を列挙するには、行 $u$ の $n$ 個の成分を全部見る必要があります。どの成分が $1$ かは事前にわからないので、$n$ 個未満しか見ないと見落としの可能性が残り、$\Theta(n)$ が必要です。全辺の走査は各行についてこれを行うので $\Theta(n^2)$ です。

(b) 領域は、頂点ごとのリストの先頭を保持する部分が $\Theta(n)$、リストの要素の総数が、無向グラフでは各辺 $\{u,v\}$ が $\mathrm{Adj}[u]$ と $\mathrm{Adj}[v]$ に 1 回ずつ現れるので 補題 2.5 より $\sum_u \deg(u) = 2m = \Theta(m)$、有向グラフでは同じく $\sum_u \deg^{+}(u)=m$ です。合わせて $\Theta(n+m)$ です。

$u$ の隣接頂点の列挙はリストを末尾までたどるだけで、要素数は $\deg u$ 個、リストが空でも先頭を見る定数時間はかかるので $\Theta(1+\deg u)$ です。全辺の走査はこれを全頂点について行うので、

$$\sum_{u \in V} \Theta(1 + \deg u) = \Theta\left(n + \sum_{u\in V}\deg u\right) = \Theta(n+2m) = \Theta(n+m)$$

となります（再び 補題 2.5 を使いました）。辺の有無の判定は $\mathrm{Adj}[u]$ を線形に探索するので、$v$ が末尾にある場合や含まれない場合に $\Theta(\deg u)$ かかります。

∎

無向単純グラフでは $m \le n(n-1)/2$ です。$m$ が $n$ に比例する程度の疎なグラフでは、隣接リストが $\Theta(n)$ 語で済むのに対し隣接行列は $\Theta(n^2)$ 語を使い、頂点数 $10^5$ の道路網なら $10^{10}$ 成分となって現実的ではありません。以降は隣接リストを前提にします。逆に $m=\Theta(n^2)$ の密なグラフでは隣接行列が有利です。

3. 幅優先探索：最短の「本数」を測る

3.1. アルゴリズム

幅優先探索（breadth-first search、BFS）は、始点 $s$ から近い順に頂点を訪れる探索です。「近い」は辺の本数で測ります。実装は、訪問予定の頂点を先入れ先出しのキュー（キュー（定義 7.1）［基本的なデータ構造］）に入れておくだけです。

from collections import deque

def bfs(adj, s):
    """adj[u] は u の隣接頂点のリスト。s は始点。"""
    n = len(adj)
    INF = float('inf')
    dist = [INF] * n          # d[v]
    parent = [-1] * n         # 最短路木の親
    dist[s] = 0
    queue = deque([s])
    while queue:
        u = queue.popleft()               # 先頭から取り出す
        for v in adj[u]:                  # u の隣接リストを 1 回だけ走査
            if dist[v] == INF:            # まだ発見していない頂点だけ
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)           # 末尾に追加
    return dist, parent

dist[v] が INF かどうかが「未発見か既発見か」の印を兼ねている点に注意してください。値は 1 度だけ書き込まれ、以後変わりません。以下、この配列を $d[v]$ と書きます。

3.2. 正当性

$d[v]$ が本当に距離 $\delta(s,v)$ に一致することを証明します。まず 2 つの不変式を用意します。

以下の補題のねらいは、キューの中に並ぶ距離の値が「ある値 $k$ と $k+1$ の 2 種類だけで、小さいほうが前」という形を保つことを示す点にあります。この形が保たれるので、頂点は距離の小さい順に取り出され、定理の証明で「近い頂点が先に処理される」と言えます。なお、証明に出てくる「空虚に真」とは、確かめる対象が 1 つもない（たとえば空のキュー）ために条件が自動的に成り立つ、という意味です。

補題 3.1（BFS の不変式）✓

グラフ $G=(V,E)$（有向でも無向でもよい）と始点 $s \in V$ について上のアルゴリズムを実行する。実行中の任意の時点で次が成り立つ。

(a) すべての $v \in V$ について $d[v] \ge \delta(s,v)$ である（$d[v]=\infty$ の場合も含む）。

(b) キューの中身を先頭から順に $v_1,v_2,\ldots,v_r$（$r \ge 1$）とすると

$$d[v_1] \le d[v_2] \le \cdots \le d[v_r] \le d[v_1] + 1$$

が成り立つ。

(c) 頂点が取り出される順に $u_1,u_2,\ldots$ と並べると $d[u_1] \le d[u_2] \le \cdots$ である。

証明（補題 3.1）

まず、辺で結ばれた 2 頂点の距離について

$$u \text{ と } v \text{ が辺で結ばれている（有向なら } (u,v)\in E \text{）} \implies \delta(s,v) \le \delta(s,u)+1$$

が成り立つことを確かめます。$\delta(s,u)=\infty$ なら右辺が $\infty$ なので自明です。$\delta(s,u)=k<\infty$ なら、長さ $k$ の $s$ から $u$ への歩道の末尾に辺 $(u,v)$ を継ぎ足すと、長さ $k+1$ の $s$ から $v$ への歩道になります。$\delta(s,v)$ は歩道の長さの最小値（定義 2.2）なので $\delta(s,v)\le k+1$ です。これを三角不等式と呼ぶことにします。

(a) 代入の回数についての帰納法で示します。初期状態では $d[s]=0=\delta(s,s)$、他の $v$ では $d[v]=\infty\ge\delta(s,v)$ なので成立します。代入が起こるのは、ある $u$ を取り出して隣接頂点 $v$ に $d[v] \leftarrow d[u]+1$ とするときだけです。帰納法の仮定より $d[u]\ge\delta(s,u)$ なので、三角不等式と合わせて

$$d[v] = d[u]+1 \ge \delta(s,u)+1 \ge \delta(s,v)$$

となり、代入後も (a) が保たれます。

(b) キューへの操作回数についての帰納法で示します。初期状態はキューが $(s)$ だけなので、$d[s]\le d[s]+1$ で成立します。

操作は「先頭 $u$ を取り出す」と「取り出した $u$ の隣接リストを走査しながら末尾に追加する」の 2 種類しかありません。$u$ を取り出す直前のキューを $(u,x_1,\ldots,x_p)$ とすると、帰納法の仮定より

$$d[u] \le d[x_1] \le \cdots \le d[x_p] \le d[u]+1$$

です。$u$ を取り出し、走査の中で新たに $y_1,\ldots,y_q$（$q\ge0$）が追加された後のキューは $(x_1,\ldots,x_p,y_1,\ldots,y_q)$ であり、追加された頂点の値はすべて $d[y_j]=d[u]+1$ です。

$p \ge 1$ のとき、この不等式の列から $d[x_1]\le\cdots\le d[x_p]\le d[u]+1=d[y_1]=\cdots=d[y_q]$ なので単調性が成り立ち、末尾の値は $d[y_q]=d[u]+1 \le d[x_1]+1$（$d[u]\le d[x_1]$ を使いました）なので先頭 $+1$ 以下です。$q=0$ のときも $d[x_p]\le d[u]+1\le d[x_1]+1$ で成立します。

$p=0$ のとき、キューは $(y_1,\ldots,y_q)$ で全要素の値が $d[u]+1$ に等しいので、単調性も末尾の条件も成り立ちます（$q=0$ ならキューは空で主張は空虚に真です）。途中の状態（$u$ の走査の途中）でも同じ議論がそのまま通ります。

(c) $i$ についての帰納法で示します。$u_{i+1}$ は取り出される瞬間にキューの先頭にいます。$u_i$ を取り出した直後のキューに $u_{i+1}$ が既に入っていた場合、$u_i$ を取り出す直前のキューは $(u_i,\ldots,u_{i+1},\ldots)$ の形なので (b) より $d[u_i]\le d[u_{i+1}]$ です。入っていなかった場合、$u_{i+1}$ はその後キューに追加されたことになりますが、次に取り出されるのが $u_{i+1}$ なのだから、追加が起きたのは $u_i$ の走査中しかありえません。このとき $d[u_{i+1}]=d[u_i]+1 > d[u_i]$ です。いずれの場合も $d[u_i]\le d[u_{i+1}]$ が成り立ちます。

∎

定理 3.2（BFS の正当性）✓

$G=(V,E)$ を有向または無向のグラフ、$s\in V$ とする。上のアルゴリズムは停止し、停止時にすべての $v\in V$ について

$$d[v] = \delta(s,v)$$

が成り立つ。さらに $v \ne s$ かつ $\delta(s,v)<\infty$ ならば、$v,\ \mathrm{parent}[v],\ \mathrm{parent}[\mathrm{parent}[v]],\ \ldots$ とたどって得られる列を逆向きに読んだものは、$s$ から $v$ への長さ $\delta(s,v)$ の道である。

証明の方針は背理法です。「$d[v]$ が本当の距離と食い違う頂点がある」と仮定し、食い違う頂点のうち本当の距離が最小のもの（最小反例）を $v$ とします。$v$ の 1 つ手前の頂点 $u$ は $v$ より近いので、最小性から $d[u]$ は正しく、$u$ が取り出されたときに $v$ の値も正しく決まるはずだ、というところから矛盾を導きます。

証明（定理 3.2）

停止性。 $d[v]$ に値が入るのは 1 回だけ（代入の条件が dist[v] == INF だから）で、キューへの追加はその代入と同時にしか起こりません。よって追加は高々 $|V|$ 回、取り出しも高々 $|V|$ 回で、ループは有限回で終わります。

到達不能な頂点。 代入は「既に $d$ が定まった頂点 $u$ から辺をたどった先」に対してしか起こらないので、$d[v]<\infty$ となった頂点は $s$ から到達可能です（代入回数についての帰納法。$d[s]=0$ で $s$ は自明に到達可能）。対偶をとれば、到達不能な $v$ では最後まで $d[v]=\infty=\delta(s,v)$ です。

到達可能な頂点。 $d[v]\ne\delta(s,v)$ となる到達可能な頂点が存在したと仮定し、その中で $\delta(s,v)$ が最小のものを $v$ とします。補題 3.1 (a) より $d[v]\ge\delta(s,v)$ なので、実際には $d[v]>\delta(s,v)$ です。

$d[s]=0=\delta(s,s)$ なので $v\ne s$ であり、$k:=\delta(s,v)\ge1$ です。長さ $k$ の $s$ から $v$ への道を取り、$v$ の 1 つ手前の頂点を $u$ とします。この道の $u$ までの部分は長さ $k-1$ の歩道なので $\delta(s,u)\le k-1$ であり、三角不等式から $k=\delta(s,v)\le\delta(s,u)+1$、すなわち $\delta(s,u)\ge k-1$ です。よって $\delta(s,u)=k-1<k$ となり、$v$ の最小性から $d[u]=\delta(s,u)=k-1$ です。特に $d[u]<\infty$ なので $u$ はキューに入り、停止性からいつか取り出されます。

$u$ が取り出された瞬間に、辺をたどって $v$ が調べられます。このとき $d[v]$ が INF なら、その場で $d[v]\leftarrow d[u]+1=k$ となり $d[v]>k$ に反します。$d[v]$ が既に定まっていたなら、その値はある頂点 $x$ が取り出されたときに $d[v]=d[x]+1$ として書き込まれたものであり、$x$ は $u$ と同時か $u$ より前に取り出されています。補題 3.1 (c) より $d[x]\le d[u]$ なので

$$d[v] = d[x]+1 \le d[u]+1 = k$$

となり、やはり $d[v]>k$ に反します。どちらの場合も矛盾するので、そのような $v$ は存在しません。

親の列。 $\mathrm{parent}[v]=u$ と書き込まれるのは $d[v]=d[u]+1$ と同時なので、$d[\mathrm{parent}[v]]=d[v]-1$ が常に成り立ちます。$v$ から親をたどると $d$ の値が 1 ずつ減るので、$\delta(s,v)$ 回で $d=0$ の頂点、すなわち $s$ に到達します（$d[x]=0$ となるのは $x=s$ だけです）。隣り合う 2 頂点は辺で結ばれているので、この列を逆向きに読めば長さ $\delta(s,v)$ の $s$-$v$ 歩道であり、$d$ の値が相異なるので頂点も相異なり、道になっています。

∎

3.3. 計算量と実行例

命題 3.3（BFS の計算量）✓

隣接リスト表現の下で、BFS は $O(|V|+|E|)$ 時間、$O(|V|)$ の追加領域で動作する。隣接行列表現の下では $O(|V|^2)$ 時間かかり、$s$ から到達可能な頂点が $\Theta(|V|)$ 個あるときは $\Theta(|V|^2)$ 時間かかる。

証明（命題 3.3）

配列 $d$ と $\mathrm{parent}$ の初期化に $\Theta(|V|)$ かかります。定理 3.2 の停止性の議論より、各頂点はキューに高々 1 回しか入らないので、append と popleft は合わせて $O(|V|)$ 回で、deque ではそれぞれ $O(1)$ 時間です。

取り出された頂点 $u$ について、隣接リスト $\mathrm{Adj}[u]$ を 1 回だけ走査します。1 つの頂点は高々 1 回しか取り出されないので、走査の総費用は 命題 2.6 (b) より $\sum_{u}\Theta(1+\deg u)=\Theta(|V|+|E|)$ で抑えられます。以上を足して $O(|V|+|E|)$ です。追加領域はキューと 2 本の配列で $O(|V|)$ です。

隣接行列表現では、頂点 $u$ の隣接頂点を列挙するのに 命題 2.6 (a) より $\Theta(|V|)$ かかり、これを取り出された頂点すべてについて行うので $O(|V|^2)$ になります。取り出されるのは $s$ から到達可能な頂点だけなので、それが $\Theta(|V|)$ 個あるときにこの評価は $\Theta(|V|^2)$ で最良になります。

∎

例 3.4（G0 に対する BFS の実行）

$G_0$ の隣接リスト（例 2.4）を上の表の順で与え、$s$ から BFS を実行します。キューの状態を、取り出しの直後・走査の直後の順に追います。

取り出す頂点	走査で新たに発見	走査後のキュー	確定した $d$
—	—	$(s)$	$d[s]=0$
$s$	$a,\ b$	$(a,b)$	$d[a]=1,\ d[b]=1$
$a$	$c$	$(b,c)$	$d[c]=2$
$b$	$d$	$(c,d)$	$d[d]=2$
$c$	$e$	$(d,e)$	$d[e]=3$
$d$	なし	$(e)$	—
$e$	なし	$()$	—

結果は $d[s]=0$、$d[a]=d[b]=1$、$d[c]=d[d]=2$、$d[e]=3$ です。実際、$s$ から $e$ への道は $s,a,c,e$ と $s,b,d,e$ と $s,b,c,e$ がありますが、いずれも長さ 3 で、これより短い道はありません（長さ 2 の道があるとすれば $s$ の隣接頂点 $a$ か $b$ が $e$ と隣接している必要がありますが、$\mathrm{Adj}[e]=\{c,d\}$ なのでそうなっていません）。

キューの $d$ 値は順に $(1,1),(1,2),(2,2),(2,3)$ で、いずれも 補題 3.1 (b) の「単調で、末尾は先頭 $+1$ 以下」を満たしています。

BFS は、辺の重みがすべて等しい場合の最短経路アルゴリズムです。重みが等しくないときは後半のダイクストラ法が必要になります。探索アルゴリズム の 二分探索（定理 3.2）［探索アルゴリズム］ が「配列の中を探す」ものだったのに対し、グラフ探索は「つながりをたどって探す」ものだと対比すると、位置づけがはっきりします。

4. 深さ優先探索：時刻の入れ子構造

4.1. アルゴリズム

深さ優先探索（depth-first search、DFS）は、行けるところまで行って、行き止まりになったら 1 歩戻る探索です。再帰で書くのが自然です。頂点に白（未発見）・灰色（発見済みで走査中）・黒（走査完了）の 3 色を付け、色が変わる時刻を記録します。

WHITE, GRAY, BLACK = 0, 1, 2

def dfs(adj):
    """adj[u] は u の隣接頂点のリスト。全頂点を始点候補として探索する。"""
    n = len(adj)
    color = [WHITE] * n
    disc = [0] * n            # 発見時刻 d[u]
    fin = [0] * n             # 完了時刻 f[u]
    back_edges = []
    time = 0

    def visit(u):
        nonlocal time
        color[u] = GRAY
        time += 1
        disc[u] = time
        for v in adj[u]:
            if color[v] == WHITE:
                visit(v)              # v は u の子になる
            elif color[v] == GRAY:
                back_edges.append((u, v))   # 後退辺
        color[u] = BLACK
        time += 1
        fin[u] = time

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return disc, fin, back_edges

visit(v) が visit(u) の中から呼ばれたとき、$v$ を $u$ の子と呼びます。こうして全頂点上に森（DFS 森）ができます。時刻は色が変わるたびに 1 進むので $2|V|$ で終わり、$d[u]<f[u]$ が常に成り立ちます。

4.2. 灰色頂点がなす道

DFS の力は、再帰呼び出しの入れ子構造がそのまま頂点の時刻の入れ子構造になることにあります。

次の補題は、「いま灰色の頂点を順に並べると、始点から現在地までの 1 本の道になる」ことと、「ある頂点が灰色の間に発見された頂点は、その頂点より先に完了する」ことを述べています。閉路検出の証明で使う道具です。

補題 4.1（灰色頂点の構造）✓

上の DFS の実行中の任意の時点について、次が成り立つ。

(a) そのとき灰色である頂点を、再帰スタックの底から順に $x_1,x_2,\ldots,x_k$ とすると、各 $i$ について $x_{i+1}$ は $x_i$ の子である。特に $x_1,x_2,\ldots,x_k$ は $G$ の歩道であり、$x_k$ は現在隣接リストを走査中の頂点である。

(b) 頂点 $v$ が灰色である間に発見された頂点 $z$（$z \ne v$）は、DFS 森において $v$ の子孫であり、$f[z]<f[v]$ を満たす。

証明（補題 4.1）

(a) 実行中に起きることは「visit(u) の呼び出し」と「visit(u) からの復帰」の 2 つだけなので、これらについての帰納法で示します。最初は灰色の頂点がなく主張は空虚に真です。

visit(v) が呼ばれるのは 2 か所です。1 つは最外側のループからで、このとき灰色の頂点は 1 つもないので、新しい列は $(v)$ の 1 個だけになり主張は成り立ちます。もう 1 つは visit(x_k) の隣接リスト走査の中で $v$ が白だった場合で、このとき $v$ は $x_k$ の子であり、$v$ が灰色になって列は $x_1,\ldots,x_k,v$ になります。帰納法の仮定と合わせて (a) が保たれます。visit(x_k) から復帰するときは $x_k$ が黒になって列の末尾が落ちるだけなので、主張は保たれます。

$x_{i+1}$ が $x_i$ の子であるということは、$x_{i+1}$ が $x_i$ の隣接リストに現れたということなので、$x_i$ と $x_{i+1}$ は辺で結ばれています。よって列は歩道です。

(b) $z$ が発見された瞬間を考えます。(a) より、そのとき灰色の列は $x_1,\ldots,x_k$ の形で、$z$ は走査中の頂点 $x_k$ の子として発見されます。いま $v$ が灰色なのだから $v=x_i$ となる $i$ があり、(a) より $x_k$ は $x_i$ の子孫（または $x_i$ 自身）なので、その子である $z$ は $v$ の子孫です。

子孫であることは、visit(z) の呼び出しが visit(v) の実行中に（入れ子になって）行われることを意味します。再帰呼び出しは内側が先に終わるので、visit(z) の復帰は visit(v) の復帰より前に起こり、$f[z]<f[v]$ です。

∎

4.3. 閉路検出とトポロジカルソート

定理 4.2（有向閉路の検出）✓

$G=(V,E)$ を有向グラフとする。次の 2 つは同値である。

(i) $G$ は有向閉路を含む。

(ii) 上の DFS の実行中に、後退辺（走査時に灰色である頂点へ向かう辺）が少なくとも 1 本記録される。

したがって DFS により、$G$ が有向閉路を持つかどうかを $O(|V|+|E|)$ 時間で判定できる。

証明の方針は次のとおりです。(ii) から (i) は、灰色の頂点が始点からの 1 本の道をなすので、そこへ戻る辺があれば輪ができる、というだけのことです。(i) から (ii) は、閉路の頂点のうち DFS が最初に発見するもの $v_0$ に注目します。$v_0$ が灰色の間に、閉路の残りの頂点がぜんぶ発見されるので、閉路の最後の頂点から $v_0$ へ戻る辺が、灰色の頂点へ向かう辺（後退辺）として必ず見つかります。

証明（定理 4.2）

(ii) $\Rightarrow$ (i)。 後退辺 $(u,v)$ が記録されたとします。これは $u$ の走査中、つまり $u$ が灰色のときに、$v$ も灰色であったということです。補題 4.1 (a) より、その時点の灰色頂点は $x_1,\ldots,x_k$ という歩道をなし、$u=x_k$（走査中の頂点）、$v=x_i$（ある $i \le k$）です。よって $x_i,x_{i+1},\ldots,x_k$ は $v$ から $u$ への歩道であり、これに辺 $(u,v)$ を継ぎ足すと $v$ に戻る長さ $1$ 以上の閉じた歩道になります。灰色頂点は相異なるので、これは有向閉路です（$i=k$、すなわち $u=v$ のときは自己ループで、これも閉路です）。

(i) $\Rightarrow$ (ii)。 $G$ が有向閉路 $C: v_0 \to v_1 \to \cdots \to v_{m-1} \to v_0$（$m\ge1$、頂点は相異なる）を含むとします。$C$ の頂点のうち DFS が最初に発見するものを、番号を付け替えて $v_0$ とします。

まず、$j=1,\ldots,m-1$ について「$v_j$ は $v_0$ が灰色である間に発見される」ことを $j$ についての帰納法で示します。

$j=1$ のとき。$v_0$ の走査中に辺 $(v_0,v_1)$ が調べられます。その瞬間 $v_1$ が白なら、そこで発見されるので主張が成り立ちます。白でないなら、$v_1$ は既に発見済みですが、$v_0$ が最初に発見された頂点なので発見時刻は $d[v_0]$ より後、かついま考えている瞬間（$f[v_0]$ より前）よりは前です。つまり $v_0$ が灰色である間に発見されています。

$j$ から $j+1$（$1\le j\le m-2$）へ。帰納法の仮定より $v_j$ は $v_0$ が灰色の間に発見され、補題 4.1 (b) より $f[v_j]<f[v_0]$ です。したがって $v_j$ の走査は $v_0$ の灰色の期間の内側で行われます。その走査中に辺 $(v_j,v_{j+1})$ が調べられ、$j=1$ の場合とまったく同じ場合分けにより、$v_{j+1}$ は $v_0$ が灰色である間に発見されます（$v_{j+1}$ も $C$ の頂点なので、$d[v_0]$ の時点では白でした）。

これで $v_{m-1}$ が $v_0$ の灰色期間中に発見されることがわかりました。再び 補題 4.1 (b) より $f[v_{m-1}]<f[v_0]$ なので、$v_{m-1}$ の走査は $v_0$ がまだ灰色のうちに行われます。その走査で辺 $(v_{m-1},v_0)$ が調べられ、$v_0$ は灰色なので、これが後退辺として記録されます（$m=1$ のときは $v_0$ の自己ループが $v_0$ の走査中に後退辺として記録されます）。

計算量。 各頂点について visit は高々 1 回呼ばれ（白のときだけ呼ばれ、直後に灰色になるため）、その中で隣接リストを 1 回走査するので、命題 2.6 (b) より総費用は $O(|V|+|E|)$ です。

∎

注意 4.3

無向グラフでこの判定をそのまま使うことはできません。辺 $\{u,v\}$ をたどって $v$ に来たあと、$v$ の走査で $u$ を見ると $u$ は灰色なので、閉路がなくても必ず後退辺が出てしまうからです。無向グラフでは「親へ戻る辺を除いて、灰色の頂点へ向かう辺があるか」で判定します。この修正版は正しく、証明は上とほぼ同じです。

具体例を挙げます。辺が $\{u,v\}$ の 1 本だけのグラフには閉路がありません。しかし $u$ から探索すると、$v$ の走査で $u$ が灰色なので、後退辺 $(v,u)$ が記録されてしまいます。「親へ戻る辺を除く」とは、この $v \to u$ のように、いまの頂点の親へ戻るだけの辺を数えない、という意味です。

例 4.4（G0 に対する DFS の実行）

$G_0$（例 2.4）の隣接リストを表の順で与え、$s$ から DFS を始めます。$s \to a \to c \to b \to d \to e$ の順に深く潜り、$e$ で行き止まりになって戻ります。時刻は次のようになります。

頂点	発見時刻 $d$	完了時刻 $f$	親
$s$	1	12	—
$a$	2	11	$s$
$c$	3	10	$a$
$b$	4	9	$c$
$d$	5	8	$b$
$e$	6	7	$d$

区間 $[d[u],f[u]]$ は $[1,12] \supset [2,11] \supset [3,10] \supset [4,9] \supset [5,8] \supset [6,7]$ と完全に入れ子になっています。これが 補題 4.1 の言う構造です。

親への辺を除くと、後退辺は $(b,s)$（$b$ の走査時に $s$ は灰色）と $(e,c)$（$e$ の走査時に $c$ は灰色）の 2 本です。それぞれ閉路 $s,a,c,b,s$ と $c,b,d,e,c$ を与えます。$G_0$ は連結で $|E|-|V|+1 = 7-6+1 = 2$ なので、独立な閉路の本数が 2 であることとも合っています。

BFS（例 3.4）が $s$ の近くから順に訪れたのに対し、DFS は $a,c,b,d,e$ と一直線に潜ります。同じグラフでも探索木の形はまったく違います。

注意 4.5

有向非巡回グラフ（DAG、有向閉路を持たない有向グラフ）では、完了時刻 $f$ の降順に頂点を並べると、すべての辺が前から後ろへ向く順序（トポロジカル順序）になります。

理由は次のとおりです。辺 $(u,v)$ を任意に取り、$u$ の走査でこの辺を調べる瞬間の $v$ の色で場合分けします。$v$ が白なら $v$ は $u$ の子になり 補題 4.1 (b) から $f[v]<f[u]$ です。$v$ が灰色なら $(u,v)$ は後退辺なので 定理 4.2 より $G$ に有向閉路が存在し、DAG であることに反します。$v$ が黒なら $f[v]$ は既に確定していて $f[u]$ はまだ確定していないので $f[v]<f[u]$ です。いずれの場合も $f[v]<f[u]$ となり、$f$ の降順では $u$ が $v$ より先に来ます。

この順序は、依存関係の解決（ビルド順序、履修順序）や、DAG 上での漸化式の計算順序を与えます。後者は 動的計画法（Dynamic Programming） の基礎になる考え方です（部分問題族と依存グラフ（定義 3.1）［動的計画法］）。

5. 重み付き最短経路とダイクストラ法

5.1. 問題設定と最適部分構造

カーナビが求めているのは「交差点を何回通るか」ではなく「所要時間の合計」です。辺に重みが付いたグラフでは、距離の定義を取り替える必要があります。

定義 5.1（重み付き最短経路）↗

$G=(V,E)$ を有向グラフ、$w:E\to\mathbb{R}_{\ge0}$ を非負の重み関数とする。歩道 $W=(v_0,\ldots,v_k)$ の重みを

$$w(W) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})$$

で定める（$k=0$ のときは $w(W)=0$）。$s,v\in V$ に対し

$$\delta_w(s,v) = \min \{\, w(W) \mid W \text{ は } s \text{ から } v \text{ への歩道} \,\}$$

を $s$ から $v$ への最短距離といい、$v$ が $s$ から到達不能なときは $\delta_w(s,v)=\infty$ と定める。最小値を与える歩道を最短路という。

重みが非負なので、この最小値は必ず存在します。歩道に同じ頂点が 2 回現れれば、その間の閉じた部分の重みは非負なので、取り除いても重みは増えません。よって最小値の候補は道だけで足り、道は有限個しかないからです。

補題 5.2（最短路の最適部分構造）✓

$w$ を非負の重み関数とする。$P=(v_0,v_1,\ldots,v_k)$ が $v_0$ から $v_k$ への最短路ならば、任意の $0\le i\le j\le k$ について、部分列 $P_{ij}=(v_i,\ldots,v_j)$ は $v_i$ から $v_j$ への最短路である。特に $\delta_w(v_0,v_j)=w(P_{0j})$ が成り立つ。

証明（補題 5.2）

重みの定義から $w(P)=w(P_{0i})+w(P_{ij})+w(P_{jk})$ と分解できます。

$P_{ij}$ が最短でないと仮定すると、$v_i$ から $v_j$ への歩道 $Q$ で $w(Q)<w(P_{ij})$ となるものが存在します。$P_{0i}$、$Q$、$P_{jk}$ をこの順につないだものは $v_0$ から $v_k$ への歩道 $P'$ であり、

$$w(P') = w(P_{0i}) + w(Q) + w(P_{jk}) < w(P_{0i}) + w(P_{ij}) + w(P_{jk}) = w(P)$$

となります。定義 5.1 では最小を歩道の全体で取っているので、これは $P$ が最短であることに反します。よって $P_{ij}$ は最短路です。$i=0$、$j$ を任意として $\delta_w(v_0,v_j)=w(P_{0j})$ を得ます。

∎

この補題は「最短路の一部分を切り出しても最短路である」と言っています。だからこそ、最短距離を短い順に 1 つずつ確定していく戦略が成り立ちます。同じ構造は 動的計画法（Dynamic Programming） の出発点でもあります（最適部分構造（定義 5.1）［動的計画法］）。

5.2. アルゴリズム

ダイクストラ法（Dijkstra, 1959）の考え方はこうです。各頂点 $v$ に暫定値 dist[v]（今わかっている最良の $s$-$v$ 歩道の重み）を持たせ、暫定値が最小の未確定頂点を選んでその値を確定させ、そこから出る辺で隣の暫定値を改善する（緩和する。より良い経路が見つかったときに暫定値を書き換えることです）。これを繰り返します。最小の頂点を取り出す操作は優先度付きキューがちょうど提供します。

Python の heapq は要素の値を後から下げる操作（decrease-key）を持たないので、改善のたびに新しい要素を押し込み、古い要素は取り出したときに捨てる遅延削除の書き方をします。

import heapq

def dijkstra(adj, s):
    """adj[u] は (v, w) のリスト（u から v への重み w の辺）。すべての w は 0 以上。"""
    n = len(adj)
    INF = float('inf')
    dist = [INF] * n
    dist[s] = 0
    pq = [(0, s)]                     # (暫定値, 頂点) の最小ヒープ
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                  # 古い要素なので捨てる
        for v, w in adj[u]:           # u から出る辺を緩和する
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

以下、取り出した要素が d > dist[u] で捨てられなかったとき、「$u$ が処理された」ということにします。

ダイクストラ法の正当性の骨格。確定済み集合 S の外に初めて出る辺 (x, y) に注目する。

5.3. 正当性

定理 5.3（ダイクストラ法の正当性）✓

$G=(V,E)$ を有向グラフ、$w:E\to\mathbb{R}$ をすべての辺 $e$ について $w(e)\ge0$ を満たす重み関数、$s\in V$ とする。このとき上のアルゴリズムは停止し、停止時にすべての $v\in V$ について

$$\texttt{dist}[v] = \delta_w(s,v)$$

が成り立つ。

証明の中心は手順 4 です。「いま取り出した頂点 $u$ の暫定値が本当の最短距離より大きい」と仮定して矛盾を導きます。$s$ から $u$ への最短路をたどると、処理済みの頂点の集合 $S$ から初めて外へ出る場所があり、外に出て最初の頂点が $y$、その直前の頂点が $x$ です。$x$ は処理済みなので、辺 $(x,y)$ はすでに緩和されており、$y$ の暫定値は正しい値になっています。ところが $u$ は「ヒープの最小」として選ばれたので、$u$ の鍵は $y$ の鍵以下です。さらに重みが非負なので、$y$ は $u$ より遠くありません。この 2 つを合わせると、$u$ の暫定値が最短距離より大きいことと食い違います。手順 2 の「鍵」とは、ヒープに入っている（暫定値、頂点）の組のうち暫定値の部分で、遅延削除のために同じ頂点の古い要素がヒープに残っていても、取り出される鍵は減らない、というのが手順 2 の内容です。

証明（定理 5.3）

手順 1（下界）。 実行中の任意の時点で、すべての $v$ について $\texttt{dist}[v]\ge\delta_w(s,v)$ が成り立ちます。代入回数についての帰納法で示します。初期状態は $\texttt{dist}[s]=0=\delta_w(s,s)$（重みが非負なので $s$ に戻る歩道の重みは 0 以上）と $\texttt{dist}[v]=\infty$ で成立します。代入は $u$ の処理中に $\texttt{dist}[v]\leftarrow d+w(u,v)$（ここで $d=\texttt{dist}[u]$）という形でしか起こらず、帰納法の仮定から $d\ge\delta_w(s,u)$ なので

$$\texttt{dist}[v] = d + w(u,v) \ge \delta_w(s,u)+w(u,v) \ge \delta_w(s,v)$$

です。最後の不等号は、$s$ から $u$ への重み $\delta_w(s,u)$ の歩道に辺 $(u,v)$ を継ぎ足せば $s$ から $v$ への歩道になることから従います。また、この式から $\texttt{dist}[v]<\infty$ ならばそれはある $s$-$v$ 歩道の重みであることもわかります。

手順 2（取り出す鍵は減らない、各頂点は高々 1 回処理される）。 取り出される鍵（ヒープの最小値）の列は非減少です。なぜなら、鍵 $d$ の要素を取り出したあとに押し込まれる鍵は $d+w(u,v)\ge d$（$w\ge0$）であり、ヒープに残っている他の要素の鍵も $d$ 以上だからです。

いま $u$ が鍵 $d_1$ で処理されたとします。このとき $\texttt{dist}[u]=d_1$ です。その後 $\texttt{dist}[u]$ が更新されるには、ある頂点 $x$ の処理中に $d_2+w(x,u)<\texttt{dist}[u]=d_1$ となる必要がありますが、$d_2$ はその時点で取り出された鍵なので $d_2 \ge d_1$、したがって $d_2+w(x,u)\ge d_1$ となり更新は起こりません。よって $\texttt{dist}[u]$ は $u$ の処理後に変化せず、以後 $u$ の要素を取り出しても鍵は $d_1$ 以上で d > dist[u] により捨てられます（鍵がちょうど $d_1$ の要素は、$u$ の処理時に取り出されたもの以外に押し込まれていません。押し込みは $\texttt{dist}[u]$ の狭義の減少と同時にしか起こらないからです）。ゆえに各頂点は高々 1 回しか処理されません。

手順 3（待機中の要素）。 実行中の任意の時点で、$\texttt{dist}[y]<\infty$ かつ $y$ が未処理ならば、ヒープには鍵 $\texttt{dist}[y]$ の $y$ の要素が入っています。実際、$\texttt{dist}[y]$ が最後に更新されたときに鍵 $\texttt{dist}[y]$ の要素が押し込まれており、もしそれが既に取り出されていたなら、取り出し時に鍵と $\texttt{dist}[y]$ が一致していたので $y$ は処理されていたはずで、未処理という仮定に反するからです。

手順 4（処理時の値は正しい）。 処理される頂点を処理順に $u_1,u_2,\ldots$ とします。「$u_i$ が処理される時点で $\texttt{dist}[u_i]=\delta_w(s,u_i)$」がすべての $i$ で成り立つことを、最小反例を取って示します。そうでない $i$ が存在するとし、最小のものを取って $u:=u_i$、$d:=\texttt{dist}[u]$ と置きます。手順 1 より $d>\delta_w(s,u)$ です。

$u_1=s$ であり $\texttt{dist}[s]=0=\delta_w(s,s)$ なので $u\ne s$ です。また $d>\delta_w(s,u)$ から $\delta_w(s,u)<\infty$、つまり $u$ は $s$ から到達可能です。そこで $s$ から $u$ への最短路 $P$ を 1 つ取ります。

$S=\{u_1,\ldots,u_{i-1}\}$（$u$ が処理される直前までに処理された頂点の集合）と置きます。$s=u_1\in S$ で $u\notin S$ なので、$P$ 上には $S$ に属さない頂点があります。その最初のものを $y$、$P$ 上での $y$ の直前の頂点を $x$ とすると、$x\in S$ です（図を参照）。

$x$ は $u$ より前に処理されているので、$i$ の最小性より $\texttt{dist}[x]=\delta_w(s,x)$ が $x$ の処理時に成り立っていました。その処理の中で辺 $(x,y)$ が緩和されるので、緩和の直後に

$$\texttt{dist}[y] \le \delta_w(s,x) + w(x,y)$$

となります。ここで 補題 5.2 を $P$ に適用すると、$P$ の $x$ までの部分は最短路なので $\delta_w(s,x)=w(P_{s\to x})$ であり、$y$ までの部分も最短路なので $\delta_w(s,y)=w(P_{s\to x})+w(x,y)=\delta_w(s,x)+w(x,y)$ です。したがって $\texttt{dist}[y]\le\delta_w(s,y)$ となり、手順 1 の下界と合わせて $\texttt{dist}[y]=\delta_w(s,y)$ です。$\texttt{dist}$ は減る一方なので、この等式は $u$ が取り出される時点まで保たれます。

$y\notin S$ なので $y$ は未処理です。手順 3 より、$u$ が取り出される瞬間、ヒープには鍵 $\delta_w(s,y)$ の $y$ の要素が入っています。$u$ の要素はそのヒープの最小値として取り出されたのだから

$$d \le \delta_w(s,y).$$

一方、$y$ は $P$ 上の頂点なので 補題 5.2 より $\delta_w(s,u)=\delta_w(s,y)+w(P_{y\to u})$ であり、重みが非負なので $w(P_{y\to u})\ge0$、したがって $\delta_w(s,y)\le\delta_w(s,u)$ です。2 つを合わせると $d\le\delta_w(s,u)$ となり、$d>\delta_w(s,u)$ に矛盾します。よって反例は存在しません。

手順 5（停止と、到達可能・不能な頂点）。 手順 2 より各頂点は高々 1 回処理され、辺 $(u,v)$ の緩和は $u$ の処理中にしか起こらないので、緩和は高々 $|E|$ 回です。押し込みは緩和が成功したときだけ起こるので高々 $|E|+1$ 回（初期の 1 回を含む）、したがって取り出しも高々 $|E|+1$ 回で、ループは停止します。

停止時にはヒープが空なので、手順 3 より $\texttt{dist}[v]<\infty$ となるすべての $v$ は処理済みで、手順 4 と手順 2（処理後は値が変わらない）より $\texttt{dist}[v]=\delta_w(s,v)$ です。逆に $v$ が $s$ から到達可能なら $\texttt{dist}[v]<\infty$ であることを、最短路 $s=p_0,p_1,\ldots,p_k=v$ に沿った帰納法で示します。$p_0=s$ は $\texttt{dist}[s]=0<\infty$ で処理されます。$p_j$ が処理されれば、その処理中に辺 $(p_j,p_{j+1})$ が緩和されて $\texttt{dist}[p_{j+1}]<\infty$ となり、手順 3 とヒープが空になることから $p_{j+1}$ も処理されます。よって $v$ も処理され $\texttt{dist}[v]<\infty$ です。対偶より、到達不能な $v$ は $\texttt{dist}[v]=\infty=\delta_w(s,v)$ のままです。

∎

5.4. 計算量

命題 5.4（ダイクストラ法の計算量）✓

隣接リスト表現と二分ヒープによる優先度付きキューを用いると、上の実装は $O(|V| + |E|\log|V|)$ 時間、$O(|V|+|E|)$ 領域で動作する。特に $|V|\ge2$ でグラフが連結（有向グラフなら $s$ から全頂点に到達可能）ならば $|E|\ge|V|-1$ なので、これは $O(|E|\log|V|)$ と書ける。

証明（命題 5.4）

定理 5.3 の手順 5 より、押し込みは高々 $|E|+1$ 回、取り出しも高々 $|E|+1$ 回です。したがってヒープに入る要素数は常に $|E|+1$ 以下で、二分ヒープの 1 回の操作は $O(\log(|E|+1))$ 時間です。単純な有向グラフでは $|E|\le|V|(|V|-1) < |V|^2$ なので

$$\log(|E|+1) \le \log(|V|^2+1) = O(\log|V|)$$

です。よってヒープ操作の総費用は $O(|E|\log|V|)$ です。

ヒープ以外の仕事は、配列 $\texttt{dist}$ の初期化に $\Theta(|V|)$、処理された頂点の隣接リストの走査に 命題 2.6 (b) より $O(|V|+|E|)$ です。合計して $O(|V|+|E|\log|V|)$ を得ます。領域はヒープが $O(|E|)$、配列が $O(|V|)$ です。

連結性の仮定の下では $|E|\ge|V|-1$ なので $|V| = O(|E|)$ であり、$|V| \le 2|E| \le 2|E|\log|V|$（$|V|\ge2$ より $|E|\ge|V|-1\ge|V|/2$ かつ $\log|V|\ge1$）から $O(|V|+|E|\log|V|)=O(|E|\log|V|)$ となります。

∎

例 5.5（重み付きグラフでの実行を最後まで追う）

次の有向グラフ $G_1$ を考えます。

重み付き有向グラフ G1。辺のラベルが重み。

$s$ を始点として実行します。ヒープの中身は鍵の昇順に書きます。

取り出した要素	判定	緩和の内訳	緩和後のヒープ
—	—	初期化	$(0,s)$
$(0,s)$	処理	$\texttt{dist}[a]\leftarrow4$、$\texttt{dist}[b]\leftarrow1$	$(1,b),(4,a)$
$(1,b)$	処理	$1+2=3<4$ で $\texttt{dist}[a]\leftarrow3$、$1+6=7<\infty$ で $\texttt{dist}[c]\leftarrow7$	$(3,a),(4,a),(7,c)$
$(3,a)$	処理	$3+3=6<7$ で $\texttt{dist}[c]\leftarrow6$、$3+6=9<\infty$ で $\texttt{dist}[d]\leftarrow9$	$(4,a),(6,c),(7,c),(9,d)$
$(4,a)$	破棄	$4>\texttt{dist}[a]=3$	$(6,c),(7,c),(9,d)$
$(6,c)$	処理	$6+1=7<9$ で $\texttt{dist}[d]\leftarrow7$	$(7,c),(7,d),(9,d)$
$(7,c)$	破棄	$7>\texttt{dist}[c]=6$	$(7,d),(9,d)$
$(7,d)$	処理	$d$ から出る辺はない	$(9,d)$
$(9,d)$	破棄	$9>\texttt{dist}[d]=7$	空

結果は $\texttt{dist}=(s:0,\ a:3,\ b:1,\ c:6,\ d:7)$ です。答え合わせをします。$s$ から $d$ への道は $s,a,d$（$4+6=10$）、$s,b,a,d$（$1+2+6=9$）、$s,a,c,d$（$4+3+1=8$）、$s,b,c,d$（$1+6+1=8$）、$s,b,a,c,d$（$1+2+3+1=7$）の 5 本で、最小は 7 です。確かに一致しています。

$a$ の暫定値が $4$ から $3$ へ下がり、古い要素 $(4,a)$ が後で破棄されている点が、遅延削除の実装の要点です。処理された頂点は $s,b,a,c,d$ の順で、これは最短距離 $0,1,3,6,7$ の昇順になっています。定理 5.3 の手順 2 が言っていたのはこのことです。

5.5. 非負性を落とすと壊れる

例 5.6（負の重みがあると正しくない）

$V=\{s,a,b\}$、辺と重みを

$$w(s,a)=1,\qquad w(s,b)=2,\qquad w(b,a)=-2$$

とします。真の最短距離は $\delta_w(s,a)=2+(-2)=0$、$\delta_w(s,b)=2$ です。

アルゴリズムを走らせます。$(0,s)$ を処理して $\texttt{dist}[a]\leftarrow1$、$\texttt{dist}[b]\leftarrow2$。ヒープは $(1,a),(2,b)$ です。次に $(1,a)$ を取り出して処理しますが、$a$ から出る辺はないので何も起こりません。次に $(2,b)$ を処理して $2+(-2)=0<1$ から $\texttt{dist}[a]\leftarrow0$ となり $(0,a)$ が押し込まれます。最後に $(0,a)$ を取り出すと $0=\texttt{dist}[a]$ なので $a$ が2 回目の処理を受けます。

この実装では最終的な $\texttt{dist}[a]=0$ は偶然正しくなりますが、$a$ が 2 回処理されており 定理 5.3 の手順 2 が破れています。頂点数が増えると処理回数は指数的に増えうるうえ、「取り出したら確定」として打ち切る標準的な実装では、$a$ の答えが $1$ になって誤ります。

原因ははっきりしています。定理 5.3 の手順 4 の最後で使った「$\delta_w(s,y)\le\delta_w(s,u)$」は、$y$ から $u$ への残りの重みが非負であることに依存していました。負の辺があると、遠回りしてから重みを取り戻す経路がありうるので、暫定値が最小の頂点を確定してよい理由が消えます。

注意 5.7

負の重みを許すなら、すべての辺の緩和を $|V|-1$ 回繰り返すベルマン・フォード法を使います。$O(|V||E|)$ 時間かかる代わりに負の辺を扱え、$|V|$ 回目にまだ緩和できる辺があれば「$s$ から到達可能な負閉路がある」（最短距離が $-\infty$ になる）ことを検出します。全点対の最短経路には、ワーシャル・フロイド法（$O(|V|^3)$）やジョンソンの方法があります。

なお「最短」ではなく「最長」の道を求める問題は、一般のグラフでは NP 困難（定義 6.1）［P≠NP 予想とは何か］ です（ハミルトン路問題が特別な場合として埋め込めます）。同じグラフの上の問題でも、少し向きを変えるだけで手に負えなくなることについては P≠NP予想とは何か を参照してください。

6. 演習

演習 6.1易

$V=\{1,2,\ldots,n\}$ を頂点集合とする有向グラフ $G=(V,E)$ の隣接行列を $A$ とする（定義 2.3）。任意の整数 $k\ge1$ について、行列 $A^k$ の $(i,j)$ 成分が「$i$ から $j$ への長さちょうど $k$ の歩道の本数」に等しいことを示してください。

解答

$k$ についての帰納法で示します。

$k=1$ のとき。$i$ から $j$ への長さ 1 の歩道とは辺 $(i,j)$ そのものなので、その本数は $(i,j)\in E$ なら 1、そうでなければ 0 です。これは定義により $A_{ij}$ に一致します。

$k$ で成り立つと仮定して $k+1$ を示します。行列の積の定義から

$$(A^{k+1})_{ij} = \sum_{l=1}^{n} (A^{k})_{il}\, A_{lj}$$

です。一方、$i$ から $j$ への長さ $k+1$ の歩道 $(v_0,\ldots,v_{k+1})$ は、最後から 2 番目の頂点 $l=v_k$ によって、「$i$ から $l$ への長さ $k$ の歩道」と「辺 $(l,j)$」の組に一意に分解されます。逆に、$l$ を任意に固定して「$i$ から $l$ への長さ $k$ の歩道」と「辺 $(l,j)$」を選べば、つなげて $i$ から $j$ への長さ $k+1$ の歩道が 1 つ得られます。この対応は全単射なので、本数は $l$ ごとの積の和、すなわち

$$\sum_{l=1}^{n} (\,i \text{ から } l \text{ への長さ } k \text{ の歩道の本数}\,)\times(\,\text{辺 } (l,j) \text{ の有無}\,)$$

に等しく、帰納法の仮定によりこれは $\sum_l (A^k)_{il}A_{lj} = (A^{k+1})_{ij}$ です。

演習 6.2標準

無向グラフ $G=(V,E)$ が二部グラフであるとは、$V=X\sqcup Y$（互いに素な和）と分割して、すべての辺が $X$ の頂点と $Y$ の頂点を結ぶようにできることをいう。

$G$ を連結な無向グラフ、$s\in V$ を任意の頂点とし、$d[v]=\delta(s,v)$ を BFS で求めた距離とする。このとき

$$G \text{ が二部グラフ} \iff \text{すべての辺 } \{u,v\}\in E \text{ について } d[u]\ne d[v]$$

が成り立つことを示し、二部グラフ判定が $O(|V|+|E|)$ 時間でできることを説明してください。

解答

$G$ は連結なので、すべての $v$ について $d[v]<\infty$ です（定理 3.2）。

($\Leftarrow$) すべての辺で $d[u]\ne d[v]$ とします。補題 3.1 の証明の冒頭で示した三角不等式を、辺 $\{u,v\}$ の両向きに使うと $d[v]\le d[u]+1$ かつ $d[u]\le d[v]+1$、すなわち $|d[u]-d[v]|\le1$ です。仮定より $d[u]\ne d[v]$ なので $|d[u]-d[v]|=1$ となり、$d[u]$ と $d[v]$ の偶奇は異なります。そこで

$$X=\{v\in V \mid d[v] \text{ は偶数}\},\qquad Y=\{v\in V \mid d[v] \text{ は奇数}\}$$

と置けば、$X\sqcup Y=V$ であり、すべての辺は $X$ と $Y$ をまたぎます。よって $G$ は二部グラフです。

($\Rightarrow$) $G$ が二部グラフで分割 $V=X\sqcup Y$ を持つとします。$s\in X$ としてよいです。まず「$s$ から $v$ への任意の歩道の長さの偶奇は、$v$ が $X$ にあるか $Y$ にあるかだけで決まる」ことに注意します。実際、歩道に沿って辺を 1 本渡るたびに $X$ と $Y$ が入れ替わるので、長さが偶数なら終点は $X$、奇数なら終点は $Y$ です。したがって $v\in X$ なら $d[v]$ は偶数、$v\in Y$ なら $d[v]$ は奇数です。

いま辺 $\{u,v\}$ を任意に取ると、二部性から一方は $X$、他方は $Y$ に属するので、$d[u]$ と $d[v]$ の偶奇は異なり、特に $d[u]\ne d[v]$ です。

判定の計算量。 BFS で $d$ を求めるのに 命題 3.3 より $O(|V|+|E|)$、隣接リストを 1 周して各辺で $d[u]\ne d[v]$ を確かめるのに $O(|V|+|E|)$、合計 $O(|V|+|E|)$ です。連結でない場合は連結成分ごとに BFS を行えば同じ評価です。

演習 6.3標準

負の重みを持つ有向グラフに対して、「すべての辺の重みに十分大きい定数 $c>0$ を足して非負にしてから、ダイクストラ法で最短路を求める」という方針を考える。この方針は正しいでしょうか。正しくないなら反例を挙げ、どこが破綻しているかを説明してください。

解答

正しくありません。反例を挙げます。$V=\{s,a,b,t\}$、辺と重みを

$$w(s,t)=2,\qquad w(s,a)=1,\qquad w(a,b)=-1,\qquad w(b,t)=1$$

とします。$s$ から $t$ への道は $s,t$（重み 2）と $s,a,b,t$（重み $1+(-1)+1=1$）の 2 本で、最短路は後者です。

すべての辺に $c=1$ を足すと、$w'(s,t)=3$、$w'(s,a)=2$、$w'(a,b)=0$、$w'(b,t)=2$ となり、すべて非負です。この新しい重みでは、$s,t$ の重みが 3、$s,a,b,t$ の重みが $2+0+2=4$ となり、最短路が $s,t$ に変わってしまいます。

破綻の理由は、定数シフトが道ごとに違う量だけ重みを増やすことにあります。辺を $k$ 本使う道は $kc$ だけ重くなるので、辺の本数が多い道が不当に不利になり、大小関係が保存されません。

正しい付け替えは、頂点ごとの関数（ポテンシャル）$h:V\to\mathbb{R}$ を使って $w'(u,v)=w(u,v)+h(u)-h(v)$ とするものです。このとき道 $u=p_0,\ldots,p_k=v$ の重みは

$$\sum_{i}\bigl(w(p_i,p_{i+1})+h(p_i)-h(p_{i+1})\bigr) = w(P) + h(u)-h(v)$$

となり、同じ端点を持つ道はすべて同じ量 $h(u)-h(v)$ だけずれるので、大小関係が保たれます。すべての辺で $w'\ge0$ となる $h$ は、注意 5.7 のベルマン・フォード法で（負閉路がなければ）求められます。これがジョンソンの方法です。

演習 6.4難

ダイクストラ法を、優先度付きキューの代わりに「未処理の頂点のうち $\texttt{dist}$ が最小のものを、長さ $|V|$ の配列の線形探索で選ぶ」方式で実装すると $O(|V|^2+|E|)$ 時間になることを確かめてください。そのうえで、命題 5.4 の二分ヒープ実装がこの配列実装より漸近的に速くなるのは、$|E|$ が $|V|$ のどのような範囲にあるときか答えてください。

解答

配列実装の評価。 外側のループは「未処理の頂点から最小の $\texttt{dist}$ を持つものを選んで処理する」を繰り返すもので、各頂点は 1 回だけ処理されるのでループは高々 $|V|$ 回まわります。1 回あたり、$|V|$ 個の要素を線形に走査して最小値を探すので $O(|V|)$ です。ここまでで $O(|V|^2)$ です。

緩和については、辺 $(u,v)$ は $u$ が処理されるときの 1 回だけ調べられ、配列に対する更新は $O(1)$ です。よって緩和の総費用は 命題 2.6 (b) より $O(|V|+|E|)$ です。初期化は $O(|V|)$ です。合計して $O(|V|^2+|E|)$ となります。単純グラフでは $|E|=O(|V|^2)$ なので、これは $O(|V|^2)$ とも書けます。

比較。 二分ヒープ実装は $O(|V|+|E|\log|V|)$、配列実装は $O(|V|^2)$ です。前者が漸近的に速いのは、o 記法（定義 3.2）［計算量と O 記法］ で書けば

$$|E|\log|V| = o(|V|^2), \qquad \text{すなわち}\qquad |E| = o\!\left(\frac{|V|^2}{\log|V|}\right)$$

のときです。

道路網のように次数が定数で抑えられるグラフでは $|E|=\Theta(|V|)$ なので、ヒープ実装が $\Theta(|V|\log|V|)$、配列実装が $\Theta(|V|^2)$ で、$|V|=10^5$ なら約 $10^6$ 対 $10^{10}$ と 4 桁の差がつきます。逆に密なグラフ $|E|=\Theta(|V|^2)$ では、ヒープ実装が $\Theta(|V|^2\log|V|)$、配列実装が $\Theta(|V|^2)$ となり配列実装が速くなります。

参考文献

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — 第 VI 部（グラフアルゴリズム）。基本的なグラフ探索、単一始点最短経路、全点対最短経路を扱う。邦訳は『アルゴリズムイントロダクション』近代科学社。
• E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik 1 (1959), 269–271. DOI: 10.1007/BF01386390 — ダイクストラ法の原論文。最小全域木の構成法と合わせて 2 ページ半で述べられている。
• M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM 34 (1987), 596–615. DOI: 10.1145/28869.28874 — フィボナッチヒープにより、ダイクストラ法を $O(|E|+|V|\log|V|)$ に改善した論文。
• J. Kleinberg and É. Tardos, Algorithm Design, Addison-Wesley, 2005 — 第 3 章（グラフ）と第 4 章（貪欲法）。BFS と DFS の性質、ダイクストラ法を貪欲法の枠組みで扱っている。
• R. Sedgewick and K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 — 第 4 章（Graphs）。実装寄りの記述と、隣接リストによるデータ構造の作り方が詳しい。
• 石畑清『アルゴリズムとデータ構造』岩波書店（岩波講座 ソフトウェア科学 3）、1989 — グラフの表現と探索の日本語の標準的な解説。

Appendix: 優先度付きキューの選び方

取り出しと値の引き下げのどちらが多いか。 ダイクストラ法が優先度付きキューに要求する操作は 2 つで、最小値の取り出しは高々 $|V|$ 回（各頂点 1 回）、値の引き下げ（decrease-key）は高々 $|E|$ 回（各辺 1 回）起こります。疎でないグラフでは後者が圧倒的に多いので、引き下げが速い構造ほど有利です。

代表的な 3 つの実装。 下の表の計算量は、上の回数と 1 回あたりの費用を掛けたものです。

実装	最小値の取り出し	値の引き下げ	ダイクストラ法全体
未整列配列の線形探索	$O(\lvert V\rvert)$	$O(1)$	$O(\lvert V\rvert^2 + \lvert E\rvert)$
二分ヒープ	$O(\log \lvert V\rvert)$	$O(\log \lvert V\rvert)$	$O((\lvert V\rvert+\lvert E\rvert)\log \lvert V\rvert)$
フィボナッチヒープ	$O(\log \lvert V\rvert)$（償却）	$O(1)$（償却）	$O(\lvert E\rvert + \lvert V\rvert\log \lvert V\rvert)$

表の「償却」とは、1 回ごとの費用ではなく、操作を何回も続けたときの 1 回あたりの平均で評価した費用のことです。フィボナッチヒープの $O(|E|+|V|\log|V|)$ は、比較に基づく実装としては漸近的に最良ですが、定数倍が大きく実装も複雑なので、実務では二分ヒープが使われることがほとんどです。各データ構造の内部については 基本的なデータ構造 を参照してください。

decrease-key を持たない言語での書き方。 Python の heapq のように値の引き下げがない場合、本文の実装のように「引き下げの代わりに新しい要素を押し込み、取り出したときに古ければ捨てる」遅延削除を使います。ヒープに入る要素数が $|V|$ ではなく $|E|+1$ まで増えますが、$\log(|E|+1)=O(\log|V|)$ なので漸近計算量は変わりません（命題 5.4）。実装が単純になるぶん、こちらが好まれることが多いと思います。