最短経路
01 / 共通の仕組み
始点から各ノードまでの最短距離を求める。仕組みは辺が何を運ぶかで分岐する — 等コストなら BFS、非負重みなら優先度付きキュー(Dijkstra)、 負を許すなら緩和を繰り返す(Bellman-Ford)、全点対距離は Floyd-Warshall。
上から一つのサブパターンを選んでください。それぞれ単独でリンクできます — 問題に一番近いものから始めましょう。
↑ 選ぶ— / どれをいつ使うか
等コスト BFS
各辺のコストが同じ場合に使う — 1 ステップ = 1 辺。
グリッド · 迷路 · O(V + E)
Dijkstra
辺の重みが非負の場合に使う。
優先度付きキュー · O((V + E) log V)
Bellman-Ford
負の重みを許すとき、または循環検出が必要なときに使う。
V−1 回の緩和 · O(V · E)
Floyd-Warshall
単一始点ではなく全点対の距離が必要なときに使う。
中継点 DP · O(V³)