http://yoshiki-utakata.hatenablog.com/
-
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1305
-
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2369
/**
* ワーシャルフロイド法
* コストが0だとエッジがないとみなされる版
*/
static void warshallFloyd(int[][] g, int n){
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i == j) continue;
if(g[i][k] == 0 || g[k][j] == 0) continue;
if(g[i][j] == 0) {
g[i][j] = g[i][k] + g[k][j];
} else {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
}
連結な無向グラフにおいて、すべての接点を連結するグラフ(木になる)のうち辺の重みの総和が最小になるもの。 プリム法というアルゴリズムもある