全点対間最短路(Warshall-Floyd)
説明
隣接行列で表されるグラフの全点間最短路を求めるアルゴリズム。負辺路が存在する場合はそれも検出する(ある頂点 $k$ から $k$ への最短路が負ならば負閉路が存在)。
使い方
- Warshall(g): 隣接行列 $g$ 上の全点対間最短路を求める
隣接行列 $g$ の各要素は最初に $INF$ で初期化しておく必要がある。ただし $INF \ge 2^{30}$ のときオーバーフローするので注意。
計算量
$O(V^3)$
$V$: 頂点数
実装例
応用 1: 辺の追加
現在のグラフに辺を追加する場合に限り, 更新を$O(N^3)$ ではなく $O(N^2)$ で行える. 追加した辺に影響する範囲のみを更新するようにする.
問題例
- 検証済AOJ GPL_1_C 全点対間最短経路
- AOJ0117 大工の褒美
- AOJ0200 青春の片道切符
- AOJ0189 便利な町
- AOJ2005 Water Pipe Construction
- AOJ2200 Mr. Rito Post Office
- AOJ1182 鉄道乗り継ぎ
- AOJ0526 船旅 (応用1)