Floyd算法

定义概览

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

算法描述

1) 算法思想原理：

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。

从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

2) 算法描述：

a. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。　　

b. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

Floyd算法过程矩阵的计算—-十字交叉法

方法：两条线，从左上角开始计算一直到右下角如下所示

给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点

相应计算方法如下：

代码实现

java 版本

核心代码只有 4 行，实在令人赞叹。

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

    // 打印
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            System.out.println(i + " " + j + ":" + a[i][j]);
        }
    }
}

正确性分析

核心代码只有四行，三行循环，一行更新，的确十分简洁优雅，可是这四行代码为什么就能求出任意两点的最短路径呢？

看代码的特点，很显然特别像是一种动态规划，确实，之前也说过该算法是基于动态规划的。

我们从动态规划的角度考虑，解动态规划题目的重点就是合理的定义状态，划分阶段，我们定义 f[k][i][j] 为经过前k的节点，从i到j所能得到的最短路径，f[k][i][j]可以从f[k-1][i][j]转移过来，即不经过第k个节点，也可以从f[k-1][i][k]+f[k-1][k][j]转移过来，即经过第k个节点。

观察一下这个状态的定义，满足不满足最优子结构和无后效性原则。

最优子结构

图结构中一个显而易见的定理：

最短路径的子路径仍然是最短路径, 这个定理显而易见，比如一条从a到e的最短路a->b->c->d->e 那么 a->b->c 一定是a到c的最短路c->d->e一定是c到e的最短路，反过来，如果说一条最短路必须要经过点k，那么i->k的最短路加上k->j的最短路一定是i->j 经过k的最短路，因此，最优子结构可以保证。

无后效性

状态f[k][i][j]由f[k-1][i][j]，f[k-1][i,k] 以及f[k-1][k][j]转移过来，很容易可以看出，f[k] 的状态完全由f[k-1]转移过来，只要我们把k放倒最外层循环中，就能保证无后效性。

满足以上两个要求，我们即证明了Floyd算法是正确的。

我们最后得出一个状态转移方程：f[k][i][j] = min(f[k-1][i][k],f[k-1][i][k],f[k-1][k][j]) ，可以观察到，这个三维的状态转移方程可以使用滚动数组进行优化。

K 为什么要放在最外层

采用动态规划思想，f[k][i][j] 表示 i 和 j 之间可以通过编号为 1…k 的节点的最短路径。

f[0][i][j] 初值为原图的邻接矩阵。

f[k][i][j]则可以从f[k-1][i][j]转移来，表示 i 到 j 不经过 k 这个节点。

也可以 f[k-1][i][k]+f[k-1][k][j] 从转移过来，表示经过 k 这个点。

意思即 f[k][i][j]=min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])

然后你就会发现 f 最外层一维空间可以省略，因为 f[k] 只与 f[k-1] 有关。

虽然这个算法非常简单，但也需要找点时间理解这个算法，就不会再有这种问题啦。

Floyd算法的本质是DP，而k是DP的阶段，因此要写最外面。

想象一个图，讨论的是要从1点到达3点，是直接走还是经过中间点2，从而确定两点之间的最短路径。

滚动数组优化

滚动数组是一种动态规划中常见的降维优化的方式，应用广泛（背包dp等），可以极大的减少空间复杂度。

在我们求出的状态转移方程中，我们在更新f[k]层状态的时候，用到f[k-1]层的值，f[k-2] f[k-3]层的值就直接废弃了。

所以我们大可让第一层的大小从n变成2,再进一步，我们在f[k]层更新f[k][i][j]的时候，f[k-1][i][k] 和 f[k-1][k][j] 我们如果能保证，在更新k层另外一组路径m->n的时候，不受前面更新过的f[k][i][j]的影响，就可以把第一维度去掉了。

我们现在去掉第一个维度，写成我们在代码中的那样，就是f[i][j] 依赖 f[i][k] + f[k][j] 我们在更新f[m][n]的时候，用到了f[m][k] + f[k][n] 假设f[i][j]的更新影响到了f[m][k] 或者 f[k][m] 即 {m=i,k=j} 或者 {k=i,n=j} 这时候有两种情况，j和k是同一个点，或者i和k是同一个点，那么 f[i][j] = f[i][j] + f[j][j]，或者f[i][j] = f[i][i]+f[i][j] 这时候，我们所谓的“前面更新的点对”还是这两个点本来的路径，也就是说，唯一两种在某一层先更新的点，影响到后更新的点的情况，是完全合理的，所以说，我们即时把第一维去掉，也满足无后效性原则。

因此可以用滚动数组优化。

优化之后的状态转移方程即为：f[i][j] = min(f[i][j],f[i][k]+f[k][j])。

求具体路径：

我们上面仅仅是知道了最短路径的长度，实际应用中我们常常是需要知道具体的路径，在Floyd算法中怎么求具体路径呢，很简单，我们只需要记录下来在更新f[i][j]的时候，用到的中间节点是哪个就可以了。

假设我们用path[i][j]记录从i到j松弛的节点k，那么从i到j,肯定是先从i到k，然后再从k到j，那么我们在找出path[i][k] , path[k][j]即可。

即 i到k的最短路是 i -> path[i][k] -> k -> path[k][j] -> k q` 然后求path[i][k]和path[k][j] ，一直到某两个节点没有中间节点为止，代码如下：

在更新路径的时候：

if(a[i][k]>temp){
    a[i][j] = temp;
    path[i][j] = k;
}

求路径的时候：

public String getPath(int[][] path, int i, int j) {
    if (path[i][j] == -1) {
        return " "+i+" "+j;
    } else {
        int k = path[i][j];
        return getPath(path, i, k)+" "+getPath(path, k, j)+" ";
    }
}

总结

Floyd算法只能在不存在负权环的情况下使用，因为其并不能判断负权环，上面也说过，如果有负权环，那么最短路将无意义，因为我们可以不断走负权环，这样最短路径值便成为了负无穷。

但是其可以处理带负权边但是无负权环的情况。

以上就是求多源最短路的Floyd算法，基于动态规划，十分优雅。

但是其复杂度确实是不敢恭维，因为要维护一个路径矩阵，因此空间复杂度达到了O(n^2)，时间复杂度达到了O(n^3)，只有在数据规模很小的时候，才适合使用这个算法，但是在实际的应用中，求单源最短路是最常见的，比如在路由算法中，某个节点仅需要知道从这个节点出发到达其他节点的最短路径，而不需要知道其他点的情况，因此在路由算法中最适合的应该是单源最短路算法，Dijkstra算法。