思想:动态规划
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
代码实现
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算法。