全点間対最短路 (Warshall Floyd)
概要
全ての頂点間の距離を求めるアルゴリズムです． 頂点 $0, \dots ,k-1$ と $i,j$ のみを使う部分グラフで $i,j$ 間の最短距離が求まっているとします． そこに頂点 $k$ が追加されたとき，$i$ から $j$ への新しい最短経路は，$k$ を通る場合と通らない場合のどちらかになります． $k$ を $0$ から $n-1$ まで動かして順に更新すると，全ての頂点間の距離が分かります．
計算量
$O(V^3)$
使い方
- 必要に応じて自分から自分への距離を 0 にする
INFの値は十分に大きな二倍してもオーバーフローしない値に設定する- 負辺が存在するときは
INFに足さない - 自分から自分への距離が負になる頂点がある場合は負の閉路が存在する
実装
Matrix WarshallFloyd(const Graph &g) {
auto const INF = std::numeric_limits<Weight>::max() / 8;
int n = g.size();
Matrix d(n, Array(n, INF));
rep(i, n) d[i][i] = 0;
rep(i, n) for (auto &e : g[i]) d[e.src][e.dst] = std::min(d[e.src][e.dst], e.weight);
rep(k, n) rep(i, n) rep(j, n) {
if (d[i][k] != INF && d[k][j] != INF) d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
}
return d;
}