Floyd-Warshall算法
Floyd算法实现
给定有向或无向图\(G\)，设\(d[][]\)是1-based的邻接矩阵（其中\(d[i][i]=0\)），则Floyd算法实现如下：
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
可以理解成：最外层循环依次用每个节点(\(k\))做中间节点，看是否能得到任意两点(\(i,j\))间的距离。经过O(\(n^3\))计算之后，就得到两两节点间的最短距离。