最短経路
01 / 共通の仕組み
始点から各ノードまでの最短距離を求める。仕組みは辺が何を運ぶかで分岐する — 等コストなら BFS、非負重みなら優先度付きキュー(Dijkstra)、 負を許すなら緩和を繰り返す(Bellman-Ford)、全点対距離は Floyd-Warshall。
01 / 一文での本質
辺の重みが非負なら、未訪問ノードのうち現在の距離が最小のものは 他の未訪問ノード経由でこれ以上短くなることがない —— だから最小優先度付きキューで毎回最も近いノードを取り出し、その出辺を緩和すれば、 1 回のパスで最短距離が確定する。
問題非負重みグラフ上の、始点からの最短経路グラフメッシュ始点A
グラフのノード数は 6。すべての距離を ∞ に初期化し、始点を優先度付きキューに入れる。
ステップ
0 / 47
優先度キュー
—
確定済み
0 / 6
0 / 47
02 / パターンの骨格
# 始点からの Dijkstra —— 非負重みdist[v] ← ∞ for all vdist[s] ← 0pq ← 最小ヒープ (0, s)while pq が空でない:(d, u) ← pq.pop_min() # 最小を取り出すif d > dist[u]: continuefor (v, w) in neighbors(u): # 緩和if dist[u] + w < dist[v]:dist[v] ← dist[u] + wpq.push((dist[v], v)) # decrease-key、もしくは重複したまま入れる
03 / このパターンを使うべき合図
「非負重み」
辺が正(あるいはゼロ)のコストを持つ —— 距離、時間、お金、レイテンシ。負の重みが入りうるなら Dijkstra は黙って誤答する。Bellman-Ford を使う。
「最小コスト / 最短距離」
目的は辺の重みの合計であって、ホップ数ではない。「最安」「合計時間最小」「最も楽な経路」 —— 経路に沿って非負コストを積み上げる問題はすべてここに含まれる。
「単一始点から複数目的地」
始点が 1 つ、すべての他ノードへの距離 —— あるいは特定の目的地への距離。 Dijkstra を 1 回走らせれば両方が得られる。目的地が 1 つだけなら、 それが取り出された時点で早期終了できる。
「優先度付きキュー / 最小ヒープ」
データ構造そのものがアルゴリズム。常に現時点の距離が最小のノードを取り出す —— 通常のキューやスタックでは動かない。重みが不揃いだと、 あるノードに最初に到達したパスが最短とは限らないからだ。
04 / よくある落とし穴
i.
負の辺を含むグラフで Dijkstra を走らせる。
一度ノードが取り出されて確定すると、Dijkstra は二度と見直さない —— しかし後で出現する負の辺によって、その距離が短くなることはありうる。 エラーは出ず、ただ静かに誤った答えを返す。負の重みが入りうるなら Bellman-Ford。
ii.
古いエントリのチェックを忘れる。
多くの実装は緩和のたびに新しい
(dist, v) をヒープに積み、 本物の decrease-key は行わない。だからヒープには古いエントリが溜まる。 取り出したら d > dist[u] なら必ずスキップすること。 さもないと同じノードを何度も処理して計算量が膨らむ。iii.
「最大 K 回乗り換え」のような制約付き問題に素の Dijkstra を使う。
Dijkstra は累積コストだけを最適化する。ホップ数や乗り換え回数の上限(LC 787)が加わると、 最短経路が最も安い経路より多くの乗り換えを必要とすることがあり、 「最小を取り出す」貪欲な前提が崩れる。 状態付き BFS、K 回緩和の Bellman-Ford、あるいは
(cost, stops) をキーにした 改造 Dijkstra に切り替える。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³)