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$)计算之后，就得到两两节点间的最短距离。

例题