如果你已经能把Dijkstra堆优化、SPFA的SLF优化写到肌肉记忆，那你大概率也被一个问题卡过：题目要求求所有点对之间的最短距离，怎么搞最稳？更麻烦的是，图里还有负权边，又不能跑Dijkstra，那怎么办？我见过不少人的第一反应是“对每个起点跑一遍单源最短路”，听着合理，但对稠密图或者带负权的图来说，这个方案很容易变得又慢又不正确。这个系列写到第11篇，我想把Floyd算法真正讲透——不是丢一段模板代码让你背，而是把它背后的状态设计、降维原理、路径回溯和边界坑全部拆开。哪怕你之前只是听说过这个名字，看完也能自己推出来，并且知道什么时候该用它、什么时候果断换别的算法。
1. 全源最短路径到底是什么问题：单源算法为什么顶不上
1.1 单源与全源的本质差别
单源最短路径，指的是固定一个起点，比如节点1，求它到图中所有其他节点的最短距离。这类问题最常用的武器是Dijkstra、Bellman-Ford、SPFA。它们的共同点是：一次计算只服务一个起点。
全源最短路径则完全不同：它要求任意两个节点之间的最短距离。这个问题至少有两种“笨办法”：
- 对每个节点都跑一次单源最短路，加起来是n次。
- 把图里所有路径枚举一遍，显然不可行。
第一种办法看起来简单，但你得先选对单源算法。假设图里有负权边，Dijkstra直接废掉，因为你不能保证“当前选出的最近节点”以后不会被一条负权边更新。你只能退回到Bellman-Ford或者SPFA，跑n次，复杂度变成O(n * n * m)级别，可以理解为三到四次层嵌套。如果图再稠密一点，m接近n^2，那总复杂度直接往O(n^4)方向走，稍微大一点的图就彻底跑不动。
所以全源最短路径不是单源最短路径的简单重复，它是一个需要重新审视的问题。Floyd算法恰好用一个极短的O(n^3)三重循环，一次性把所有点对的距离都算出来。
1.2 Floyd算法在这种问题里的位置
Floyd算法的思维出发点是“路径拼接”。设想i到j之间有一条最短路径，这条路径上可能经过一堆中间节点。如果能逐步放宽“允许经过的中间节点集合”，并不断修正任何两点之间的最短路，那么最终收敛时，所有点对距离就是全源最短路径。
这也是Floyd算法最吸引人的地方：所有操作都在一张邻接矩阵上进行。你不需要建邻接表，不需要优先队列，不需要处理复杂的出队入队。只需要一张二维表，然后三层循环把表刷到稳定。
此外，Floyd对负权边天然免疫。只要图里没有负环，Floyd就能给出正确结果，这是Dijkstra做不到的。负权边在实际建模中并不少见，比如某些目标函数是“收益费收益”的转换，两个状态之间的转移代价可能是负值。
我自己的使用经验里，Floyd还有一个隐藏优势：跑完之后，任意两点之间的最短距离是O(1)查询。后续不管做动态规划、聚类、还是多组询问，直接查表，不需要再碰图结构。这比“现场临时跑一次Dijkstra”要好用很多，尤其是查询次数非常多的时候。
2. 三层循环背后的状态推导：从三维DP到二维原地更新
2.1 经典状态设计：允许经过哪些中间节点
很多人背Floyd的时候只知道三重循环长这样：
for k in 1..n for i in 1..n for j in 1..n dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])但完全不知道这个k到底是什么。我从动态规划的角度给你拆开。
定义一个三维状态：
- dp[k][i][j] 表示从i到j，只允许经过编号为1到k的节点作为中间节点时，最短路径长度。
注意dp[0][i][j]是什么？中间节点一个都不允许经过，那只能从i直接走到j。如果存在边，就是边权；不存在边，就是正无穷。所以初始化时，把邻接矩阵直接当作dp[0]。
然后考虑dp[k][i][j]。当你把第k个节点加入“允许的中间节点集合”后，从i到j的最短路径只可能分成两种：
- 完全不用第k个节点作为中间节点，此时路径长度仍然是dp[k-1][i][j]。
- 用第k个节点作为中间节点，路径分为两段：i先到k，再从k到j，长度是dp[k-1][i][k] + dp[k-1][k][j]。
所以状态转移方程是：
dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])这个方程是整个Floyd算法的灵魂。所有的三重循环，不过是在按k从小到大填这个三维表。
2.2 为什么原地更新是安全的
三维表二维化，这是初学者最容易困惑的地方。按理说，dp[k]的计算用到了dp[k-1]的值，如果我用一个二维数组原地更新，会不会把还没用上的旧值覆盖掉，导致结果出错？
答案是不会，但需要证明。核心关键是看dp[k][i][k]和dp[k][k][j]这两个值。
先从定义出发：dp[k][i][k]表示从i到k，只允许经过前k个节点作为中间节点的最短距离。这里的端点也是k。如果这条路径中间又经过了k，就会形成“走一圈回来”的效果，比如i到某个节点，再到k，再回到k。最短路径里，这种重复经过同一个中间节点的环一定可以去掉，去掉后距离不会变大。所以真正的最短路径并不会把k当作自己的中间节点再用一次。
因此：
- dp[k][i][k]实际上等于dp[k-1][i][k]
- dp[k][k][j]实际上等于dp[k-1][k][j]
现在再回到更新dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。表面上我们读的dist[i][k]和dist[k][j]可能是已经被第k轮更新过的值，但刚才证明了它们更新后的值跟更新前完全一样，所以用二维数组原地更新是严格等价的。
这也是为什么Floyd的循环顺序必须是k在最外层，i和j在内层随意。如果反过来，把i或者j放最外层，k放内层，这个等价性就不成立，结果会错得莫名其妙。
2.3 一个更容易记住的直观解释
如果你觉得上面的形式化推导太绕，可以换一个生活化的比喻。把节点想象成一群联系人，消息只能通过联系人之间互传。一开始，每个人只知道和直接认识的人怎么联系。现在开始“开会”，第1个人被拉进核心群，全网更新的规则是：任何人的消息如果经过1号中转会更短，就改成这条新路线。然后是2号加入，全网再更新一遍。每加入一个人，消息中转的可能性就更丰富。
Floyd里的k，本质就是“当前核心群最后一个加入的人”。每加入一个人，就要重新审视所有点和所有点之间的路径：要不要通过这个新加入的家伙绕一下？这个过程重复n次，所有可能的中间节点组合都考虑完了，距离自然收敛到全局最短路。
这样想，三重循环就不再是无脑嵌套，而是一个清晰的“逐人加入、全网更新”过程。
3. 手写一版能跑的Floyd：初始化、三重循环、路径回溯
3.1 邻接矩阵初始化：重边、自环和无向图对称性
写Floyd之前，邻接矩阵的初始化直接决定你会不会在细节上翻车。
- 自己到自己的距离初始化为0，即dist[i][i] = 0。
- 没有边的位置初始化为一个很大的数，一般叫INF。
- 如果输入存在重边，保留最小的那条。不能直接赋值，要用min。
- 如果是无向图，加边时双向都要写；有向图则只写方向。
- 如果出现自环且权值为正，dist[i][i]应该还是0，因为最短路径没必要绕自己一圈。如果自环权值是负的，dist[i][i]会被更新成负数，这就是负环的信号，后面专门说。
路径矩阵的初始化和dist同步。我用path[i][j]表示从i到j这条路径上的“第一跳节点”，初始时如果i可以直接到j，第一跳就是j。这样将来还原路径时，从i出发查第一跳，再查第一跳的下一跳，一直查到j为止。
3.2 核心代码：C++和Python两种版本
C++版本可以直接存邻接矩阵，缺点是最多容纳几百到几千个节点，再大内存就吃紧。代码写法如下。
#include <bits/stdc++.h> using namespace std; const int MAXN = 505; const int INF = 0x3f3f3f3f; int dist[MAXN][MAXN]; int nxt[MAXN][MAXN]; // nxt[i][j] 表示从i出发到j的第一跳节点 void init(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) dist[i][j] = 0; else dist[i][j] = INF; nxt[i][j] = j; } } } void add_edge(int u, int v, int w) { dist[u][v] = min(dist[u][v], w); // 重边取最小 } void floyd(int n) { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { if (dist[i][k] == INF) continue; // 小优化：跳掉不可能的路径 for (int j = 1; j <= n; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; nxt[i][j] = nxt[i][k]; } } } } } void print_path(int u, int v) { if (dist[u][v] == INF) { cout << "no path" << endl; return; } int cur = u; while (cur != v) { cout << cur << " -> "; cur = nxt[cur][v]; } cout << v << endl; }Python版本更简洁，适合快速验证思路：
import sys def floyd(n, dist): nxt = [[j if i != j else None for j in range(n)] for i in range(n)] for k in range(n): for i in range(n): if dist[i][k] == float('inf'): continue for j in range(n): new_dist = dist[i][k] + dist[k][j] if new_dist < dist[i][j]: dist[i][j] = new_dist nxt[i][j] = nxt[i][k] return dist, nxt注意C++版里的INF用了0x3f3f3f3f，这是一个经典取值，约等于10.6亿。两个这样的INF相加大约是21.2亿，还在int的表示范围内，不会立即溢出成负数。这一点比直接用int的最大值要安全很多，后面我还会细讲。
3.3 用4节点的图手工推一遍矩阵变化
光看代码还是不够直观，我拿一个非常小的例子走一遍。
图里有4个节点，编号从1到4。边如下：
- 1到2权重3
- 2到3权重2
- 1到3权重8
- 3到4权重1
- 2到4权重7
初始dist矩阵（行是起点，列是终点）：
| 起点/终点 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 3 | 8 | INF |
| 2 | 3 | 0 | 2 | 7 |
| 3 | 8 | 2 | 0 | 1 |
| 4 | INF | 7 | 1 | 0 |
一开始只有直达边。
k=1，也就是允许节点1作为中间节点。走一遍i和j，发现没有哪个路径能通过节点1获得明显优势。比如2到3，原来直接是2，如果绕1，3+8=11，反而更差。矩阵不变。
k=2，允许节点2作为中间节点。这时1到3有两条路：直达8，或者1到2再到3，代价3+2=5，所以dist[1][3]更新为5。同样，1到4原本不可达，现在1到2再到4，3+7=10，所以dist[1][4]从INF变成10。3到1也对称更新为5，4到1更新为10。
k=3，允许节点3作为中间节点。此时1到4的路可以走1到3再到4，5+1=6，比原来的10更短，于是dist[1][4]更新为6。2到4也可以走2到3再到4，2+1=3，比原来的7更短，dist[2][4]更新为3。同理4到1、4到2也分别被刷新。
k=4，允许节点4作为中间节点。因为4只连了3，几乎所有路径都没变短，最终矩阵稳定。
最终结果是：
| 起点/终点 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 3 | 5 | 6 |
| 2 | 3 | 0 | 2 | 3 |
| 3 | 5 | 2 | 0 | 1 |
| 4 | 6 | 3 | 1 | 0 |
1到4的最短路径是1 -> 2 -> 3 -> 4，总距离6。这就是Floyd一步一步“松弛”出来的结果。
3.4 路径还原：维护next数组的三个关键点
距离算完之后，如果题目只是求长度，那到此为止。但很多场景要求输出具体路径，这时候next数组就必须维护好。
第一个关键点：初始化时，nxt[i][j] = j，意思是默认从i直接跳到j。如果i和j之间根本没有边，这个默认值也没关系，因为dist是INF，路径还原时会先判断不可达。
第二个关键点：更新dist[i][j]的时候，必须同步更新nxt[i][j] = nxt[i][k]。为什么是这个值？因为新路径是i先走到“到k路径上的第一跳”，然后再从k走到j。所以从i出发后第一步要走的节点，就是nxt[i][k]。
第三个关键点：访问nxt[cur][v]的时候，cur会不断变化，但v始终保持终点不变。这样做是为了沿着第一跳链走到终点。如果dist是INF，就不要进入这个循环，否则可能死循环。
很多人在更新距离时忘了维护路径矩阵，等要输出路径才发现根本没法还原，只能重新跑一遍BFS。别问我是怎么知道的。
4. 负权边、负环与INF：Floyd最容易被坑的三个细节
4.1 能处理负权不能处理负环：差在哪
Dijkstra为什么一碰到负权边就失效？因为它的贪心策略是“当前距离最近的节点一旦确定，就不再更新”，但负权边可能让一个节点在已经确定后又被一条新路径变得更短。Floyd没有这个贪心假设，它枚举了所有可能的中间节点组合，所以负权边对它来说只是普通的边权。
但是，负环是另一回事。如果图中存在一个环，环上总权重为负，那么沿着这个环反复转圈就能让路径代价无限减小。这种情况下，最短路径没有意义，不存在所谓的收敛结果。
Floyd可以检测负环。原理很简单：跑完正常的Floyd后，如果存在某个i满足dist[i][i] < 0，说明从i出发绕一圈回来，距离变成负的，那就说明存在负环。
为什么会这样？正常情况下dist[i][i]初始是0，任何正权环都会让dist[i][i]保持0或者变成更大的正数，只有负环能让它变成负数。所以只要在Floyd结束之后扫描一遍对角线，就能知道图里有没有负环。
如果你想在计算过程中就发现负环，可以加一个判断：当dist[i][k] + dist[k][j] < dist[i][j]更新之后，顺便检查dist[i][i]是否小于0。一旦发现，直接停止计算，因为后面所有结果都没有意义。
4.2 无穷大的选取与溢出陷阱
一开始学Floyd的人经常直接写INF = 1e9，或者干脆用int最大值。这两种都有隐患。
先说int最大值2147483647。如果dist[i][k]和dist[k][j]都是这个值，那dist[i][k] + dist[k][j]会直接溢出成负数。一旦出现负数，它必然小雨当前的dist[i][j]（除非dist[i][j]也是负数），结果就是因为你没判断INF，错误地把一个“不可达”的路径更新成了负数。这个问题极其隐蔽，跑小样例可能没事，随机大图一来就全错。
再说1e9。两个1e9相加等于2e9，在int范围内但已经非常接近上限。虽然大部分时候不会溢出，但如果你在不该加的时候加了，判断不出来，还是会污染矩阵。
正规做法有两个：
- 在加法之前先判断dist[i][k]和dist[k][j]是否为INF，是就跳过。
- 把INF设为0x3f3f3f3f，这样两个INF相加仍然是int范围内的正数，不会溢出不致于污染，然后靠“小于dist[i][j]”这个判断来过滤，因为正常真实路径很难超过这个值。
我自己的模板里会两种都做：既判断，又用0x3f3f3f3f。多写一行判断，能省掉一晚上的排查时间。
4.3 规模红线：什么时候果断放弃Floyd
Floyd的复杂度O(n^3)，这是它最大的天花板。给你一个粗略的体感估算：
- 当n = 300时，2700万次更新，C++轻松跑完，Python也还算能接受。
- 当n = 500时，1.25亿次更新，C++大概1秒上下，Python会明显变慢。
- 当n = 1000时，10亿次更新，C++也要好几秒甚至更多，Python基本不可行。
所以在竞赛或者面试题里，看到n <= 300到500这个量级，Floyd是正常选项；看到n超过1000，就要立刻转头想别的办法。内存也别忘了：两张n*n矩阵各占4字节的话，n=1000时是8MB，n=3000时是72MB，n=5000时直接200MB，很容易超出内存限制。
很多初学者养成了“看到邻接矩阵就无脑Floyd”的习惯，这是不对的。Floyd适合小规模全源最短路，不适合大图。这一点必须时刻记住。
5. 选型对比与变体扩展：Floyd、Dijkstra、Bellman-Ford与Johnson怎么选
5.1 四个算法的横向对比
| 算法 | 典型复杂度 | 适用场景 | 负权边 | 负环检测 | 备注 |
|---|---|---|---|---|---|
| Floyd | O(n^3) | 小规模全源最短路 | 支持 | 能 | 实现极短，查询O(1) |
| n次Dijkstra（堆优化） | O(n * m log n) | 稀疏图全源最短路 | 不支持 | 不能 | 图中不能有负权 |
| 单次Bellman-Ford | O(n * m) | 单源最短路、负环检测 | 支持 | 能 | 全源需要跑n次 |
| Johnson | O(n * m log n) | 稀疏图全源最短路 | 支持 | 能 | 通过重赋权消掉负权再跑n次Dijkstra |
这张表里最容易被忽略的是Johnson算法。它的思路是先跑一次Bellman-Ford给每个点算势能，然后把所有边重赋权成非负值，最后做n次Dijkstra。在稀疏图里，Johnson通常比Floyd划算得多。
5.2 我做选型的判断流程
现在拿到一道最短路题目，我不会急着写Floyd，而是按下面这套顺序判断：
- 如果是单源问题，直接进单源算法支线：无负权用Dijkstra，有负权用Bellman-Ford或SPFA，要判负环就用Bellman-Ford。
- 如果是全源问题，先看n的大小。n小到500以内，再问自己：图里有没有负权？有负权且稠密，优先Floyd。有负权但很稀疏，可以考虑Johnson。无负权且稀疏，n次Dijkstra更稳。
- 如果后续有大量“任意两点距离”的查询需求，这时候就算n稍微大一点，只要内存放得下，我也会倾向用Floyd先预处理，因为查询O(1)太省事了。
举个例子，状态压缩DP里经常要预先算好所有城市之间的最短路，然后每步都查两个城市之间的代价。这种情况下，Floyd的预计算结果就是整个DP的地基，极其合适。
5.3 传递闭包与bitset优化：Floyd思想的变形
Floyd的思想不只用于求最短路，还能用于求有向图的传递闭包，也就是判断任意两点之间是否存在可达路径。此时把边权换成布尔值“0/1”，转移方程变成：
reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])如果要追求极致优化，可以使用bitset，把一行压成一个整数。转移变成：
if (reach[i][k]) reach[i] |= reach[k];这样一次可以处理一个整数位，复杂度近似O(n^3 / 64)。n达到2000甚至3000都有机会跑过去。这种变形在求祖先关系、依赖关系、闭包判断的题目里非常好用。
6. 实战感悟与测试方法：从会背代码到真正用对
6.1 看到什么题干特征，第一反应该用Floyd
刷题多了之后，你会发现Floyd出场的信号非常明显：
- 题干明确说“任意两点之间的最短路径”。
- 输入直接给了邻接矩阵。
- n在500以下，甚至只有300以内。
- 图里可能有负权边，但保证无负环。
- 后面还有大量询问，需要快速查询点对距离。
- 题目是图论与其他专题的组合，比如状态压缩DP、最小生成树变体等。
只要同时满足其中几项，Floyd基本就是最佳选择。
6.2 对拍测试与易错点核对表
写算法最忌讳“我觉得没问题”。我自己的习惯是写一个暴力版本和Floyd对拍。
具体做法是随机生成一个小图，节点数10以内，边随机加，权重随机取正负。然后写一个全排列暴力或者每次BFS/枚举所有路径的版本，跟Floyd的结果对比。跑上千组随机样例，距离相等，路径也还原正确，才算这个实现真的靠谱。
下面这张表是我每次写完Floyd都要过一遍的检查清单：
| 易错点 | 典型症状 | 解决办法 |
|---|---|---|
| INF设置过大或过小 | 出现负数或错误更新 | 用0x3f3f3f3f，并在加算前判断INF |
| 重边只赋最后一条 | 距离偏小或偏大 | 加边用min |
| 自环处理错误 | 正自环导致奇怪结果 | 初始化dist[i][i]=0 |
| 无向图只加了单向边 | 结果不对称 | 加边时双向写入 |
| 更新距离不更新next矩阵 | 路径还原错误 | 同步维护nxt[i][j]=nxt[i][k] |
| 路径不可达时强行还原 | 死循环 | 先判断dist[u][v]是否为INF |
| 负环未检测 | 距离不断变小无意义 | 扫描dist[i][i] < 0 |
把这张表贴在代码模板旁边，每次写完都对照一遍，能省很多Debug时间。
6.3 个人体会：Floyd在工程里远比想象中好用
很多人觉得Floyd只是竞赛里的小玩具，实际工程项目里没人用。我自己的体会恰恰相反。有一次我做一个规模约300个节点的距离矩阵预处理任务，节点之间有的有直接关系，有的没有，关系权重里还存在负数。如果每次查询都去临时跑Dijkstra，响应时间根本没法看。但用Floyd把所有点对距离一次性算完，后续任何查询都是查表，代码量小，结果稳定，排查问题也方便。
还有一次是在一个图论模型里，需要判断两个节点之间能否通过中间节点串联，当时直接用了传递闭包的bitset优化版本，一次跑完所有可达性。Floyd思想的可迁移性真的被低估了。
最后分享一个小技巧：学Floyd的时候，别急着背代码，先自己在纸上写三维状态的转移方程，然后想一想“为什么二维原地更新没事”。等你想明白了，再去看代码，你就能清楚地知道k、i、j三层的顺序为什么必须是那样。到这个程度，Floyd才算真正长在你脑子里，而不是停留在收藏夹里的一串字符。
