最短経路
01 / 共通の仕組み
始点から各ノードまでの最短距離を求める。仕組みは辺が何を運ぶかで分岐する — 等コストなら BFS、非負重みなら優先度付きキュー(Dijkstra)、 負を許すなら緩和を繰り返す(Bellman-Ford)、全点対距離は Floyd-Warshall。
01 / 一文での本質
各辺のコストが同じなら、あるノードに最初に到達した瞬間が そこへの最短経路 —— だから BFS(ノードをステップ数の昇順に訪れる)はそのまま最短経路アルゴリズムになる。
問題等コストグラフ上の、始点からの最短経路グラフメッシュ始点A
グラフのノード数は 6。すべての距離を ∞ に初期化し、始点をキューに入れる。
ステップ
0 / 40
キュー
—
訪問済み
0 / 6
0 / 40
02 / パターンの骨格
# 始点からの BFS —— 各辺の重み = 1dist[v] ← ∞ for all vdist[s] ← 0queue ← [s]while queue が空でない:u ← queue.pop_front()for v in neighbors(u):if dist[v] = ∞:dist[v] ← dist[u] + 1; queue.push(v)# 最初の訪問 = 最短距離。キューが層ごとに外向きに空になるため
03 / このパターンを使うべき合図
「等コストグラフ」
辺に重みがない、もしくはすべての重みが等しい。グリッド上を 1 マスずつ動く問題もここに含まれる — グリッドは暗黙のグラフ。重みが異なると BFS は最短を返さなくなる。
「最小ステップ数」
目的が「コスト」ではなく「ホップ数」。「最少手数」「最少操作」「最短列」など。
「迷路の最短路」
グリッドの定型句。4 近傍(または 8 近傍)で 1 マスの移動が 1 ステップになる。
「マルチソース BFS」
すべての始点を距離 0 で一度に入れて BFS を 1 回 — 各始点で個別に走らせるより遥かに安い。
04 / よくある落とし穴
i.
「DFS の方が簡単」と DFS を選ぶ。
DFS は何らかの順序で訪れるが、距離順ではない —— 最初に到達したパスが長いこともある。 等コストの最短経路には必ずBFS。
ii.
取り出し時に訪問済みフラグを立て、入れる時には立てない。
v をキューから取り出すときにだけ visited[v] = true にすると、 同じノードがキューに何度も入りうる —— 密グラフで二乗的に膨らむ。入れるときに立てる。iii.
BFS が「非負・等コスト」専用だと忘れている。
辺の重みが違った瞬間に BFS は誤答する。Dijkstra を使う (重みが 0/1 だけなら、両端キューで 0-1 BFS)。
05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。
— / どれをいつ使うか
等コスト BFS
各辺のコストが同じ場合に使う — 1 ステップ = 1 辺。
グリッド · 迷路 · O(V + E)
Dijkstra
辺の重みが非負の場合に使う。
優先度付きキュー · O((V + E) log V)
Bellman-Ford
負の重みを許すとき、または循環検出が必要なときに使う。
V−1 回の緩和 · O(V · E)
Floyd-Warshall
単一始点ではなく全点対の距離が必要なときに使う。
中継点 DP · O(V³)