最短経路
01 / 共通の仕組み
始点から各ノードまでの最短距離を求める。仕組みは辺が何を運ぶかで分岐する — 等コストなら BFS、非負重みなら優先度付きキュー(Dijkstra)、 負を許すなら緩和を繰り返す(Bellman-Ford)、全点対距離は Floyd-Warshall。
01 / 一文での本質
すべての辺を繰り返し緩和する —— V−1 回まわせば、 最短経路(辺数は高々 V−1)はすべて見つかる。たとえ一部の辺が負重みでも。
問題単一始点最短経路、負重みを許すグラフ負あり始点A
グラフのノード数は 5 —— 緩和ラウンドを 4 回まわす。すべての距離を ∞ に初期化。
ステップ
0 / 66
ラウンド
0 / 4
直近の緩和
変化なし
負閉路
—
0 / 66
02 / パターンの骨格
# 始点からの Bellman-Ford —— 負重みを許すdist[v] ← ∞ for all vdist[s] ← 0# V−1 ラウンド —— 最短経路の辺数は高々 V−1for round in 1 .. V−1:for (u, v, w) in edges:# 緩和if dist[u] + w < dist[v]:dist[v] ← dist[u] + w# 負閉路の検出 —— もう一度回すfor (u, v, w) in edges:if dist[u] + w < dist[v]: return "負閉路あり"
03 / このパターンを使うべき合図
「負の辺重み」
最も決定的な合図。コストが負になりうる —— 返金、利益、為替アービトラージなど。このとき Dijkstra は安全でない。標準ツールは Bellman-Ford。
「負閉路の検出」
V−1 ラウンドを回した後、もう 1 回追加で回す。まだ緩和できる辺があれば、始点から到達可能な負閉路が存在する。
「高々 K 本の辺 / K 回の経由」
緩和ラウンドを V−1 ではなく K に切り詰める。K ラウンド後の
dist[v] は「辺数が高々 K の最短経路」になる —— Bellman-Ford の定番の使い方。「アービトラージ / 為替」
−log(rate) を辺重みにすると、負閉路は利益が出るループに対応する —— Bellman-Ford でそのまま検出できる。04 / よくある落とし穴
i.
負の辺を含むグラフに Dijkstra を使う。
Dijkstra は一度確定したノードを後の負辺で更新できない —— 警告もなく誤答する。 辺重みに負がありうるなら、必ず Bellman-Ford(あるいは SPFA / Johnson 法)を使うこと。
ii.
V−1 ラウンドで止めて、負閉路の検出をしない。
V−1 ラウンド後に距離が確定するのは、始点から到達可能な負閉路がないときだけ。 必ずもう 1 ラウンド追加で回す:まだ緩和される辺があれば、答えは数値ではなく「負閉路あり」になる。
iii.
dist[u] = ∞ のときの dist[u] + w オーバーフロー。dist[u] がまだ無限大の場合は緩和をスキップする —— そうしないと ∞ + (−w) が有限値に巻き戻り、距離配列を静かに壊しうる。 加算の前にガードを入れること。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³)