ワーシャル・フロイド法

目的

頂点数$n$の有向グラフに対して、任意の頂点間の最短路の長さを$O(n^3)$で列挙します。

計算量

$O(n^3)$

使い方

int n
頂点数
double[][] dist
コード中の「update dist here」において、頂点uからvに向かう辺の長さをdist[u][v]の初期値として設定してください。頂点uからvに向かう辺が存在しないときは$\infty$を初期値として設定してください。(ただし実際に$\infty$を代入することはできないので、実用的には十分大きい数で代替する必要があります。Double.MAX_VALUEを使用するとちょっとした拍子のオーバーフローが恐いので、Double.MAX_VALUE/3を使うことが多いです)。

ソースコード

class Main {
    void run() {
	int n = -1;
	double[][] dist = new double[n][n];

	// update dist here

	for (int k = 0; k < n; k++) {
	    for (int j = 0; j < n; j++) {
		for (int i = 0; i < n; i++) {
		    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	    }
	}
    }
}