最短経路
01 / 共通の仕組み
始点から各ノードまでの最短距離を求める。仕組みは辺が何を運ぶかで分岐する — 等コストなら BFS、非負重みなら優先度付きキュー(Dijkstra)、 負を許すなら緩和を繰り返す(Bellman-Ford)、全点対距離は Floyd-Warshall。
01 / 一文での本質
中継点 k を処理し終えた時点で、dist[i][j] は{0, …, k} の中の点だけを中継として使う i から j への最短経路 —— だから (k, i, j) の三重ループを回せば、すべての点対が最終的な最短距離に収まる。
問題重み付きグラフの全点対最短路グラフダイヤV4
A
B
C
D
A
0
1
4
∞
B
1
0
∞
3
C
4
∞
0
1
D
∞
3
1
0
グラフのノード数は 4、有向辺は 8 本。初期 dist:対角は 0、辺は重み、その他は ∞。
ステップ
0 / 137
k
—
(i, j)
—
直近更新
—
0 / 137
上のプリセットを選んでください —— Floyd-Warshall は全点対なので始点の指定はありません。
02 / パターンの骨格
# Floyd-Warshall —— 全点対最短路dist[i][j] ← ∞ for all i, jdist[i][i] ← 0 for all idist[u][v] ← w for each edge (u, v, w)# 三重ループ:k は最も外側for k in [0, V):for i in [0, V):for j in [0, V):if dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] ← dist[i][k] + dist[k][j]# k 回目の反復が終わった時点で、k が許される最大の中継点番号
03 / このパターンを使うべき合図
「全点対最短路」
単一始点ではなく、すべての点対の距離が欲しい。各点から Dijkstra を走らせると O(V · (V + E) log V);Floyd-Warshall なら O(V³) で済み、内側は二行だけ。
「小さくて密なグラフ」
V が小さい(高々数百)。三乗のコストが支配的だが定数倍は極めて軽い —— Floyd の主要ループは数回の配列参照と 1 回の比較だけ。
「推移閉包 / 到達可能行列」
+ を OR に、min を AND に置き換えれば、 同じ三重ループでどの点対が連結かを求められる。形は同じ、半環が違うだけ。「連鎖比率 / 積型の経路」
「経路コスト」が結合的な演算子で合成できるとき(比率の積、ビット AND、最小値の最大)、 Floyd の三行更新はそのまま一般化できる —— 演算子だけ差し替えて構造はそのまま。
04 / よくある落とし穴
i.
k を最も外側以外に置く。DP 不変式 —— 「dist[i][j] は {0…k} 内の中継点だけ使う」 —— が成立するのは、すべての (i, j) について k を確定させてから次の k に進むからこそ。 k を内側に入れると途中結果と最終結果が混ざり、答えが狂う。
ii.
∞ + x を普通の数として扱う。実コードでは
INT_MAX + w はオーバーフローする。1e9 のような番兵を使うか、足す前に if dist[i][k] != ∞ and dist[k][j] != ∞ で守る。この可視化は読みやすさのため ∞ をそのまま表示している。iii.
負閉路が結果を壊すことを忘れる。
負閉路が到達可能でなければ、負辺があっても Floyd は依然として正しい。 実行後、ある i で
dist[i][i] < 0 なら負閉路あり —— 対角を見れば検出できる。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³)