floyd 算法模板详解(适合新手)

假设n为节点个数d[i][j]为从 i 到 j 的最小距离为d[i][j], INF为无穷大;

先对floyd做初始化:

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= n; j ++ )
        if (i == j) d[i][j] = 0;
        else d[i][j] = INF;

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点很好理解

那包括k点如何理解?

我们只需要把从 i -> j 其中走过的节点包括k看为从i -> k + 从k -> j ;

经过上述分析我们的代码变为：

for (int k = 1; k <= n; k ++ )
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            d[k][i][j] = min(d[k][i][j], d[k - 1][i][k] + d[k - 1][k][j]);

现在我们考虑如何对它做优化

对比我们得到的两个等式：

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
d[k][i][j] = min(d[k - 1][i][j], d[k - 1][i][k] + d[k - 1][j][k]);

假设第一个式子当i == k时变为d[k][j] = min(d[k][j], d[k][k] + d[k][j])其中d[k][k]我们初始化为了0

所以得d[k][j] = min(d[k][j], d[k][j]);我们发现当循环到第k层时这个式子就是其本身：

当j == k时同理;

所以当到第k层循环时d[k][i][j]始终为d[k - 1][i][j]因此根据背包问题得优化第一维可直接去掉，即得到最终式子

floyd算法性质：d[i][j] = min(d[i][j], d[i][k] + d[k][j])其中k是从 i 走到 j 中的最大的点