概要

グラフ上の全ての頂点間の最短経路を探す。

• 負のコストがあっても使える。
• 負の閉路があった場合検出できる。
• 頂点を三重ループする。
• 計算量は頂点数を $V$ としたときに $\mathrm{O}(V^3)$

実装

void warshall_floyd(int n) {
	for(int k=0;k<n;++k){ // 経由する頂点 k 
		for(int i=0;i<n;++i){ // 始点 i 
			for(int j=0;j<n;++j){ // 終点 j
				dist[i][j] = min(dist[i][j],d[i][k] + dist[k][j]);
			}
		}
	}
}

dist には頂点 $u,v$ 間の辺のコストを入れておく。 $u=v$ のときは $0$ を、$u,v$ 間のパスが存在しないときは inf を入れておく。

解説

実装のコードに合わせて $i$ から $j$ へのパスの最短ルートを求めることを考える。

• 頂点 $i,j$ へのパスのコスト dist[i][j]
• 頂点 $i,k$ へのパス、頂点 $k,j$ へのパス dist[i][k] + dist[k][j]

この2つを比較するために三重ループしているだけである。

名前からして難しそうなアルゴリズムだけどやっていることも中身も超単純。

と思ったけど正当性の証明ができないかもしれません。参考をちゃんと読み込んでおきます。