なぜBFSは最短路を見つけるのか ― 波紋のアナロジー

BFS が最短路を見つける理由を「波紋」の比喩で直感的に理解します．DFS が最短路を保証しない反例，Dijkstra 法が「重み付きの波紋」である理由も解説します．

2026年2月27日

BFS（幅優先探索）が最短路を見つけることは，アルゴリズムの教科書に当然のように書いてあります．しかし，なぜ幅優先に探索するだけで最短路が得られるのでしょうか？ DFS ではなぜダメなのでしょうか？この記事では，「波紋」というアナロジーを使って，BFS の正当性の本質に迫ります．

1 波紋のアナロジー

静かな水面に石を落とすと，波紋が同心円状に広がっていきます．波紋はすべての方向に同じ速度で広がるので，ある地点に最初に到達した波は，必ず最短距離を通ってきたものです．

BFS はまさにこの波紋と同じことをしています．

始点 $s$ から「波紋」を広げると，次のように層が形成されます：

距離 0： ${s}$ （始点自身）
距離 1： ${A, B}$ （ $s$ の隣接頂点）
距離 2： ${C, D, E}$ （距離1の頂点の隣接頂点のうち未訪問のもの）
距離 3： ${F}$ （距離2の頂点の隣接頂点のうち未訪問のもの）

BFS のキュー構造が，この「層ごとの展開」を正確に再現します．距離 $k$ の頂点をすべて処理し終えてから，距離 $k + 1$ の頂点の処理に移ります．

2 BFS の正当性 ― なぜ波紋は嘘をつかないのか

BFS が最短路を正しく求めることの核心を述べます．

定理 1 (BFS の最短路性).

無向グラフ

G = (V, E)

において，始点

s

から BFS を実行したとき，各頂点

v

に対して BFS が最初に

v

を発見した時点での距離ラベル

d [v]

は，

s

から

v

への最短距離

δ (s, v)

に等しくなります．

直感的な理由は次の通りです．

注意 2 (波紋の原理).

BFS では，距離

k

の頂点は距離

k - 1

の頂点からのみ発見されます．頂点

v

が最初に発見されるのは，

v

に到達する最短路の最後の辺をたどったときです．なぜなら：

もし距離 $k$ 未満で $v$ に到達できるなら，距離 $k$ の層を処理する前に $v$ はすでに発見済みのはずです
BFS はキュー（FIFO）を使うので，距離の小さい頂点が必ず先に処理されます

ポイントは，重みなしグラフでは各辺のコストが一定（すべて1）だということです．波の速度が一定だからこそ，最初に到達した波が最短なのです．

3 DFS が最短路を見つけない反例

DFS（深さ優先探索）は「一本道をとことん進んでから引き返す」探索です．これは波紋とは全く違う動きをします．

例 3 (DFS の失敗例).

以下のグラフで

s

から

t

への最短路を考えます．

最短路は

s \to t

（距離1）です．しかし DFS が

s

から先に

A

を訪問すると，

s \to A \to B \to t

（距離3）という遠回りの路を先に見つけてしまいます．

t

はすでに訪問済みとなるため，直接辺

{s, t}

を使った最短路は発見されません．

DFS の問題は，「深く潜る」ことを優先するため，近い頂点を飛ばして遠い頂点を先に訪問してしまうことです．波紋ではなく，迷路を壁伝いに歩くようなものです．

4 重み付きグラフ ― Dijkstra は「重みつきの波紋」

辺に重み（距離・コスト）がある場合，BFS の単純な波紋は通用しません．辺の重みが異なるので，「1ステップ = 1距離」という前提が崩れるためです．

例 4 (BFS が失敗する重み付きグラフ).

s \to A

の重み 1，

s \to B

の重み 10，

A \to t

の重み 100，

B \to t

の重み 1 とします． BFS は辺数（ホップ数）で最短路を求めるため

s \to A \to t

（コスト101）を選びますが，真の最短路は

s \to B \to t

（コスト11）です．

ここで登場するのがDijkstra 法です．

注意 5 (Dijkstra = 可変速度の波紋).

Dijkstra 法は，BFS の「すべての辺を等しく扱う」という制約を外し，「コストの小さい辺を先に処理する」ように変更したものです．優先度付きキュー（ヒープ）を使い，現時点で最もコストの小さい頂点を次に処理します．

これは波紋のアナロジーで言えば，「重みの軽い辺ほど波が速く伝わる」ということです．最初にある頂点に到達した波は，やはり最短コストの経路を通ってきたものになります．

定理 6 (Dijkstra 法の正当性（直感）).

辺の重みがすべて非負のとき，Dijkstra 法は正しく最短路を求めます．これは以下の貪欲選択性質に基づきます：「まだ確定していない頂点のうち，暫定距離が最小のものを確定してよい」．

なぜ非負重みが必要かも，波紋で理解できます．もし負の重みの辺があると，「すでに通り過ぎた場所に後から安いコストで到達できる」ことがあり得ます．波紋が逆流するようなもので，到達順序がコスト順序を保証しなくなるのです．

5 計算量の意味 ― なぜ $O (V + E)$ なのか

BFS の計算量 $O (∣ V ∣ + ∣ E ∣)$ は，「各頂点を1回ずつ訪問し，各辺を1回ずつ調べる」ことを意味します．

注意 7.

これは本質的に「グラフ全体を1回見る」のと同じコストです．最短路を求めるのにグラフ全体を見る必要があるのは直感的に明らかですから，BFS の計算量は最適と言えます．

Dijkstra 法の計算量 $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$ （二分ヒープ使用時）は，BFS に比べて $lo g ∣ V ∣$ 倍のオーバーヘッドがあります．これはヒープ操作のコストで，「波紋の速度が辺ごとに異なる」ことの代償です．

6 まとめ

BFS は「等速の波紋」です．辺の重みが均一だから，最初に到達 = 最短距離
DFS は「壁伝い」なので最短路を保証しません
Dijkstra は「可変速の波紋」で，非負重みの場合に最短路を求めます
負辺がある場合は波紋の比喩が破綻し，Bellman-Ford のような別のアプローチが必要になります

次の記事では，グラフの中でも特に美しい構造である「木」について考えます．

グラフ理論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

なぜBFSは最短路を見つけるのか ― 波紋のアナロジー

1 波紋のアナロジー

2 BFS の正当性 ― なぜ波紋は嘘をつかないのか

3 DFS が最短路を見つけない反例

4 重み付きグラフ ― Dijkstra は「重みつきの波紋」

5 計算量の意味 ― なぜ $O (V + E)$ なのか

6 まとめ

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

1 波紋のアナロジー

2 BFS の正当性 ― なぜ波紋は嘘をつかないのか

3 DFS が最短路を見つけない反例

4 重み付きグラフ ― Dijkstra は「重みつきの波紋」

5 計算量の意味 ― なぜO(V+E)なのか

6 まとめ

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ

5 計算量の意味 ― なぜ $O (V + E)$ なのか