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算法过程矩阵的计算—-十字交叉法

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

先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k列和对角线上的元素是不发生改变的(对角线上都是0,因为一个顶点到自己的距离就是0,一直不变;而当k为中间点时,k到其他顶点(第k行)和其他顶点到k(第k列)的距离是不变的

因此每一步中我们只需要判断4*4-3*4+2=6个元素是否发生改变即可,也就是要判断既不在第k行第k列又不在对角线上的元素。具体计算步骤如下:以k为中间点(1)“三条线”:划去第k行,第k列,对角线(2)“十字交叉法”:对于任一个不在三条线上的元素x,均可与另外在k行k列上的3个元素构成一个2阶矩阵x是否发生改变与2阶矩阵中不包含x的那条对角线上2个元素的和有关,若二者之和小于x,则用它们的和替换x,对应的Path矩阵中的与x相对应的位置用k来替代。

给出矩阵,其中矩阵A是邻接矩阵,而矩阵Path记录u,v两点之间最短路径所必须经过的点(指的是u->….->该点->v)

分别以每一个点作为K点转接v

image
image
image
image

代码实现

java 版本

核心代码只有 4 行,实在令人赞叹。  [java]

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] ,一直到某两个节点没有中间节点为止,代码如下:

在更新路径的时候:  [java]

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

求路径的时候:  [java]

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算法。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注