最短路問題の種類
- 単一始点最短路問題
- 負の重みがあるグラフ: ベルマン・フォード法
- 負の重みがない: ダイクストラ法
- DAG: トポロジカルソートをしてDP
- 特に木であればただの木上のDP（トポロジカルソート不要）
- 重みが1: BFS
- 全点対間最短路問題
負辺・負閉路の扱い
- 負辺があっても、負閉路がなければ最短路は求まる
- 負閉路があっても、始点から負閉路に到達できなければ最短路は求まる
- 始点から到達可能な負閉路があっても、負閉路から終点に到達できなければ最短路は求まる
ベルマンフォード法
‣
ダイクストラ法
‣
01-BFS
- 辺のコストが0 or 1の場合に使える
- 壁があったら壊す。壊すときにコスト1とする。普通に通過できるところはコスト0で移動する
- なにか魔法を使って特殊な移動をする
- 問題例