#创作计划# Floyd算法
2026-03-07 16:16:47
发布于：广东
19阅读
0回复
0点赞
看啥看，原来写贝尔曼-福特结果被 @Eucatastrophe 抢先写完了。
注：下文中如未特殊标明，n表示节点数量，m表示边数量。
有人曰：不如看Wiki。
我承认这篇东西确实对于高级人类来说太简单了。
请深色食用。
前言
依旧边学边写。
正文
What Is Floyd
Floyd 算法可用于求解全源最短路问题。
复杂度高得要命（时间&未优化的空间均如此）。
但是非常好实现。
可以处理负权边，但不能处理负环。
Floyd 的原理与实现
定义一数组f[k][x][y]，表示只允许经过编号为 ~ 的节点，从点 到点 的 最短路 长度。
显然f[n][x][y]就是点 到点 的最短路长度。
那么接下来轮到求解f的值了。
初始条件
f[0][x][y]有三种情况：
- 到 的边的边权，当 到 有边时
- ，当 时
- ，当且 到 没有边时
运算
对于f[k][x][y]，有以下方式更新其值：
- 不经过新的点 ，直接使用
f[k-1][x][y]的值； - 经过新的点 ，即
f[k-1][x][k] + f[k-1][k][y]。
因为我们要求最短路，所以将这两个值取min。
也就是：
f[k][x][y] = min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
最后输出。
代码实现
邻接矩阵存图。
首先初始化f[0]：
for(int x = 1;x <= n;x++){
for(int y = 1;y <= n;y++){
if(x==y) f[0][x][y]=0;
else if(g[x][y]) f[0][x][y]=g[x][y];
else g[x][y]=1e9; //1e9即INF
}
}
接下来，遍历k,x和y。
一定不能变换顺序！
for(int k = 1;k <= n;k++)
for(int x = 1;x <= n;x++)
for(int y = 1;y <= n;y++)
f[k][x][y] = min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
总代码：
void Floyd(){
for(int x = 1;x <= n;x++){
for(int y = 1;y <= n;y++){
if(x==y) f[0][x][y]=0;
else if(g[x][y]) f[0][x][y]=g[x][y];
else f[0][x][y]=1e9; //1e9即INF
}
}
for(int k = 1;k <= n;k++)
for(int x = 1;x <= n;x++)
for(int y = 1;y <= n;y++)
f[k][x][y] = min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
}
补充：Floyd 的空间优化
显然，f数组是一个三维数组，空间复杂度。
如何优化？
很简单。再次观察更新：
f[k][x][y] = min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
显然，f[k]的所有元素都是根据f[k-1]的元素更新而来。
所以，我们可以直接砍掉第一维，变成f[x][y]（类似背包 dp 的滚动数组优化）。
优化代码如下：
void Floyd(){
for(int x = 1;x <= n;x++){
for(int y = 1;y <= n;y++){
if(x==y) f[x][y]=0;
else if(g[x][y]) f[x][y]=g[x][y];
else f[x][y]=1e9; //1e9即INF
}
}
for(int k = 1;k <= n;k++)
for(int x = 1;x <= n;x++)
for(int y = 1;y <= n;y++)
f[x][y] = min(f[x][y],f[x][k]+f[k][y]);
}
后记
Floyd 的特点：时间和空间复杂度高。
但是——
它简单啊！
---全文完---
想看我下期写 Johnson 的点赞，过 3 就去写。
正在制作美丽图片。
有帮助，赞一个