先别急着背模板。Floyd-Warshall算法（简称Floyd）是我在实际工程里用过次数最多的“多源最短路径”方案——十几行代码就能解决全图任意两点之间的最短路，比跑n次Dijkstra要省心得多。但正因为代码短，很多人反而不理解它为什么能正确工作，更不知道怎么写才算“最优C++实现”。这篇文章我就从动态规划的本质开始拆，把三层循环的顺序、INF选值、路径重建、负环检测、最小环和传递闭包这些衍生玩法都讲一遍，最后给出我自己在项目里打磨过的工程级代码。适合刚学完图论想加深理解的同学，也适合要写竞赛或业务代码但不想踩坑的人。
1. 拆掉黑盒：Floyd算法的本质是动态规划
1.1 状态怎么定义，转移怎么来
初学Floyd时看到三层循环，第一反应是“这玩意儿怎么就对了”。其实它的逻辑核心是动态规划，只不过状态定义比普通背包问题抽象一点。
定义d[k][i][j]表示：从节点 i 到节点 j，中间只允许经过编号不超过 k 的节点时，所能得到的最短路径长度。这里的关键词是“允许经过的节点集合”，不是“恰好走k步”，很多人这里就混淆了。初始时d[-1][i][j]就是图的原始边权，即不经过任何中间节点（也就是直接相邻或不可达）。
当我们需要把节点头 k 纳入可用的中间节点集合时，从 i 到 j 的最短路只有两种选择：
- 不经过节点 k：那结果就是
d[k-1][i][j]； - 经过节点 k：路径被拆成 i -> ... -> k 和 k -> ... -> j，而这两段各自也只允许经过编号不超过 k-1 的中间节点，所以是
d[k-1][i][k] + d[k-1][k][j]。
两者取最小值，就得到了转移方程：
d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])这个方程特别像背包里的“选或不选”：节点 k 作为新的中转站，要么用要么不用。当 k 从小到大地扫完所有节点，d[n-1][i][j]就是真正意义上的全图最短路，因为允许经过的候选中间节点已经是全集了。
1.2 为什么k必须在外层循环
这是Floyd最容易写错、也最值得讲清楚的一点。网上很多人直接背“k在最外层，i和j在内层”，但不知道为什么，一旦自作聪明调换顺序，结果就奇奇怪怪。
核心原因是动态规划的阶段问题。第 k 轮更新d[i][j]时，公式里用了d[i][k]和d[k][j]，这两个值必须是上一阶段（只允许经过编号不超过 k-1 的中间节点）算好的结果。如果 k 循环放在最内层，那么在同一个外层迭代轮次里，d[i][k]可能已经被本轮刚纳入的节点 k 更新过了，这种“更新后的值又参与更新”的行为，相当于允许路径中反复经过同一个刚加入的中转点，把动态规划的阶段语义彻底破坏了。
有个很生动的类比：Floyd像是逐步解锁“中转城市名单”。一开始名单是空的，只能直飞；后来允许经过0号城市中转，算一遍；再允许1号城市中转，再算一遍；每解锁一个新城市，所有点对距离就基于上一版名单重新压缩一次。如果你把k循环放内层，等于名单还没完全解锁，就急着用刚解锁的城市来回绕行，结果当然不可信。
所以记住：k是阶段，不是普通索引，它必须在最外层。这也是我调代码时第一个检查的点。
1.3 复杂度、负权、适用边界
Floyd的时间复杂度是 O(n^3)，空间复杂度是 O(n^2)。n 代表节点数。这个复杂度决定了它不是万能的：
- 当 n ≤ 500 时，Floyd非常舒服，随便写都能跑进时间限制；
- 当 n = 800~1000 时，常数写得差的版本就会开始吃力；
- 当 n 超过 2000，基本不建议再用Floyd，除非你的图极其特殊。
它支持负权边，这是很多单源算法做不到的。但有前提：图中不能存在负权环。因为如果存在负环，最短路径会不断绕圈变小，没有下界。Floyd不会报错，但它会在循环中把值越算越小，最后得到一堆可疑的负大数。判断方法我在后面的章节会细说。
适用场景上，Floyd最适合“需要全源最短路 + 图规模不大”的场合。比如地图导航系统中的所有城区节点对、社交网络中的多源距离矩阵、课程设计里的任意两点最短路径查询，这些场景一次Floyd算完，之后O(1)查表，体验极佳。
2. 把思想落到代码：最稳的基础C++实现
2.1 图的存法与INF的坑
Floyd基于邻接矩阵实现，不是邻接表。用邻接矩阵直接索引任意两点间的边权，三层循环里才能高效更新。C++里习惯用vector<vector<int>>，但如果追求极致性能，后续章节会讲到一维平铺。
初始化矩阵时，原题目里没有的边要填一个“无穷大”，不能填0，否则会把不存在的路径当成0长度的路径。这个“无穷大”的选取在C++里是个经典坑。
最差的写法：
const int INF = INT_MAX;一旦执行d[i][k] + d[k][j]，而d[i][k]和d[k][j]都是INT_MAX时，直接整型溢出变成负数，min反而选中这个负数，程序彻底乱套。很多初学者的“玄学Bug”就是这么来的。
推荐的选值有两个方案：
const int INF = 0x3f3f3f3f;十进制约 10.6 亿，两个相加约 21.2 亿，仍然小于INT_MAX的 21.47 亿，不会溢出。这是竞赛圈最常用的值，因为它还能配合memset(d, 0x3f, sizeof(d))把整个矩阵批量初始化为INF，非常方便。const int INF = INT_MAX / 2;同样能保证两个INF相加不溢出，不过不能直接memset成同一个字节模式，得写循环赋值。
我个人的习惯是：如果边权范围小、确定在 int 内，用0x3f3f3f3f；如果担心路径长度会超过 int，干脆全部用long long，INF 取0x3f3f3f3f3f3f3f3f。代码里统一一个常量名，别到处散落魔法数字。
初始化时还有一个隐藏细节：
for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) d[i][j] = 0; else d[i][j] = INF; } }d[i][i]必须设成0，否则从自己到自己的最短距离会被算成绕一圈的路径，负环检测也会失灵。读入边的时候，如果是无向图，要对d[u][v]和d[v][u]同时赋值；如果题目告诉你可能有重复边，记得取最小值，别直接覆盖。
2.2 朴素版实现与正确性验证
下面是基础版代码，只知道“k在最外层”的人就能写出来。这段代码的正确性我做了充分测试，可以作为标准模板使用：
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; void floyd(vector<vector<int>>& d, int n) { for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { if (d[i][k] == INF) continue; // 关键剪枝，避免无效运算 for (int j = 0; j < n; ++j) { if (d[k][j] == INF) continue; d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } }这里的剪枝很值得一说。如果d[i][k]是INF，说明 i 到 k 根本不可达，那d[i][k] + d[k][j]无论如何都不可能是有效路径，直接跳过。这个优化看起来很朴素，但在图中大量节点不相连时，能省非常多的时间。注意别在d[i][j] == INF时跳过更新，因为min里可能算出一个有限的更小值，是必须更新的。
验证正确性最直接的办法是拿一个已知答案的小图，打印每一步的矩阵变化。这个习惯比背任何模板都有用，下一节我就带大家手算一遍。
2.3 一个四节点样例，手把手演算一遍
假设图里有 0、1、2、3 四个节点，初始边权如下：
- 0 -> 1 距离 3
- 0 -> 3 距离 7
- 1 -> 2 距离 2
- 1 -> 3 距离 1
- 2 -> 3 距离 1
其余边为INF。肉眼就能看出 0 -> 3 的最短路不是直连的7，而是 0 -> 1 -> 3，总长 3 + 1 = 4。
Floyd是怎么算出来的呢？
初始阶段（k还没开始）：d[0][3] = 7。
当 k = 0 时，节点0作为中转站。但因为0是起点，用它中转并没有带来新路径，矩阵不变。
当 k = 1 时，允许节点1作为中转。此时观察：
d[0][1] + d[1][2] = 3 + 2 = 5，小于当前d[0][2]（INF），所以更新d[0][2] = 5；d[0][1] + d[1][3] = 3 + 1 = 4，小于当前d[0][3] = 7，所以更新d[0][3] = 4。
当 k = 2 时，允许节点2作为中转。检查d[0][2] + d[2][3] = 5 + 1 = 6，但6比已经得到的4大，所以不更新。
当 k = 3 时，节点3作为中转，不会改变 0 -> 3 的最短路径。
最后d[0][3] = 4，正确。这个过程完美展示了“逐渐放开中转节点集合”的动态规划含义，每次 k 增加，矩阵里都沉淀了新的最短路径信息。
3. 最优C++实现：从模板到工程级的核心优化
3.1 关于循环顺序和缓存命中的真相
网上关于Floyd“最快写法”的争论从来没停过。最常见的说法是内层循环顺序用i, k, j比i, j, k快，因为d[i][k]是固定值，可以把d[i][k]提取到寄存器中，然后连续遍历j，对缓存友好；而i, j, k的内层 k 会不断在不同行之间跳跃，缓存命中率差。
这个说法在绝大多数现代CPU和编译器下基本成立。但注意，Floyd的正确性要求 k 在最外层而不是内层，所以“把 k 放最内层”这种层面上的所谓优化是绝对不能碰的。我们讨论的是 k 在外层固定的前提下，内层 i 和 j 的先后顺序。经过大量实测，for k -> for i -> for j本身就是经典顺序。若想进一步压榨性能，可以把二维矩阵“摊平”成一维数组，然后通过指针操作减少vector的多层封装的寻址开销。
一个典型的高性能版本：
void floyd_fast(int* d, int n) { for (int k = 0; k < n; ++k) { int* pk = d + k * n; // k行首地址 for (int i = 0; i < n; ++i) { int dik = d[i * n + k]; if (dik == INF) continue; int* pi = d + i * n; for (int j = 0; j < n; ++j) { int nd = dik + pk[j]; if (nd < pi[j]) pi[j] = nd; } } } }这里我把d[i][k]提前取到局部变量dik，把pi和pk的指针也算好，内层循环只做加法与比较。编译器通常会把这个循环自动向量化，运行性能非常可观。如果图规模较大且追求极致，还能用OpenMP把外层 i 循环并行化：因为第 k 轮更新时，不同 i 行之间互不依赖，数据竞争只存在于同一行的不同元素，所以并行是安全的。
不过在绝大多数业务代码和课程项目中，这种微优化不是瓶颈，最重要的还是代码清晰和正确。我自己的习惯是：平时用vector<vector<int>>基础版，只有在 n 逼近500~800且评测机压力大时才切换一维指针版。
3.2 INF选型与溢出保护的细节
前面提过0x3f3f3f3f的好处，这里再深入一点。为什么不是1e9或者INT_MAX/2？
用1e9（十亿）做INF时，两个1e9相加是2e9，虽然没超INT_MAX，但如果图里面路径需要“拼”三段以上，后一次加法就可能超过21亿，风险依然存在。而INT_MAX/2大约10.7亿，两个相加约21.5亿，刚好卡在溢出边缘，多次加法的风险同样不小。
用0x3f3f3f3f时，两个值相加约21.2亿，同样接近极限。为什么还要选它？一方面是因为memset(d, 0x3f, sizeof(d))可以把 int 数组按字节快速填满，每个int都变成0x3f3f3f3f，省掉写两重循环；另一方面，实际图论题里 INF 的含义只是“足够大”，只要保证两个有限边权相加不会达到这个数量级，同时两个INF相加不溢出，就很稳妥。换句话说，INF既要大于可能出现的最大路径长度，又不能大到让加法溢出。0x3f3f3f3f是这两者之间很经典的平衡。
如果使用long long，INF取0x3f3f3f3f3f3f3f3f，数值约4.6e18，远大于 int 下能累积的路径长度，两个相加也不会超过LLONG_MAX（约9.2e18）。一句话建议：凡是边权可能超过 2e9 的场景，直接用 long long 数组，别犹豫。
3.3 路径重建：让Floyd不只是返回距离
很多教程只讲距离矩阵，不讲怎么还原具体路径。但真实场景里，我们往往不仅要知道0到3最短是4，还想知道走的是0 -> 1 -> 3。这时候需要额外维护一个next矩阵。
定义nxt[i][j]表示从 i 到 j 的最短路径上，i 之后的下一个节点是谁。初始化时：
for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { nxt[i][j] = j; // 默认直连 } }当发现d[i][j]可以被d[i][k] + d[k][j]更新时，说明路径 i -> ... -> k -> ... -> j 更优，那从 i 出发的第一个跳点就继承自 i 到 k 路径上的第一个跳点，也就是：
if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; nxt[i][j] = nxt[i][k]; }重建路径时：
vector<int> reconstruct_path(int u, int v, vector<vector<int>>& nxt) { if (nxt[u][v] == -1) return {}; // 不可达 vector<int> path; path.push_back(u); while (u != v) { u = nxt[u][v]; path.push_back(u); } return path; }这个方案在 Floyd 每次更新矩阵时同步更新nxt，最终得到一个“任意两点路径跳转表”。代价是多一个n*n的 int 数组，对于 n ≤ 500 的规模完全可以接受。我在实际项目里经常用这个版本，比后来再跑别的算法去寻路径省事得多。
3.4 无向图的对称优化与剪枝细节
如果处理的是无向图，距离矩阵天然对称：d[i][j] == d[j][i]。理论上可以让 j 只遍历一半，然后同时更新对称位置，能省大约一半的内层计算。但这个优化有个前提：必须同时更新d[i][j]和d[j][i]，否则后续轮次的读取就会因矩阵不对称而出错。
if (d[i][k] != INF && d[k][j] != INF) { int nd = d[i][k] + d[k][j]; if (nd < d[i][j]) { d[i][j] = nd; d[j][i] = nd; nxt[i][j] = nxt[i][k]; nxt[j][i] = nxt[j][k]; } }很有意思的是，很多人在无向图里只更新d[i][j]，因为觉得矩阵对称后面反正会一样，但中途第三层循环读到d[k][j]时，可能恰好读到尚未更新的那个对称元素，结果就错了。这属于调试起来很痛苦的隐蔽Bug，我踩过一次之后，直接把“无向图必须对称更新”写进了自己的模板注释里。
另外一个常用剪枝是顺序遍历 j 前判断d[i][k] == INF。这个剪枝在稀疏图中收益很大，在完全图中几乎没有收益，但对正确性无影响，所以默认加上没坏处。
4. Floyd的衍生问题与排查技巧
4.1 负环检测与极值陷阱
Floyd能跑负权图，但绝对不能跑负环图。怎么检测负环呢？
跑完三层循环后，检查矩阵对角线：
bool has_negative_cycle = false; for (int i = 0; i < n; ++i) { if (d[i][i] < 0) { has_negative_cycle = true; break; } }原理很简单：d[i][i]本来初始化为0，含义是“从 i 出发，绕一圈回到 i”的最短路径之和。如果存在负环，那这个值会被更新成负数。一旦发现，直接说明图里存在至少一个负环，Floyd的结果就不可信了。
极值陷阱主要集中在三点：
- 输入边权可能很大，比如
1e9，路径累计三四个边就可能溢出 int，尤其用了不合理的INT_MAX作为INF时； - 自环的处理：如果输入
d[i][i] = -5，这就是负环信号；如果输入d[i][i] = 5，要按“自己到自己距离0”处理，需要单独覆盖； - 重复边：读入时
d[u][v] = min(d[u][v], w)，而不是直接=，否则样例里给两条重复边时就出错。
4.2 传递闭包与最小环
Floyd算法思想上的变体非常多，最常用的两个是传递闭包和最小环。
传递闭包解决的是“可达性”问题，也就是判断任意两点之间是否存在路径，不管路径多长。这时可以把距离矩阵替换成布尔矩阵：
vector<vector<bool>> reach(n, vector<bool>(n, false)); for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) if (reach[i][k]) for (int j = 0; j < n; ++j) reach[i][j] = reach[i][j] || reach[k][j];这其实就是把min换成逻辑或，把加法换成逻辑与。在 C++ 里还能用bitset把内层循环压成位运算，大幅提升性能，这里不展开。
最小环问题稍微复杂一点。它的目标是找图中总权最小的环。经典做法是在 Floyd 外层循环进入第 k 轮之前，先枚举所有 i、j（都小于k），用尚未被 k 更新的矩阵信息去更新答案：
int ans = INF; for (int k = 0; k < n; ++k) { for (int i = 0; i < k; ++i) { for (int j = i + 1; j < k; ++j) { ans = min(ans, d[i][j] + g[i][k] + g[k][j]); } } // 然后再执行正常的 floyd 更新 for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }这里g保存原始边权矩阵，d是动态更新的最短路径矩阵。为什么必须在更新之前枚举？因为如果先更新了d，d[i][j] + g[i][k] + g[k][j]可能把“经过k的最短路”和“又回到k的边”混在一起，破坏环的语义。最小环公式的意义是：从 i 到 j 的最短路（只经过小于k的节点），加上两条直达 k 的边，正好构成一个经过 k 的环。如果你需要在无向图中求至少三个节点的最小环，这个模板可以直接套。
4.3 典型Bug速查与数据规模选型
下面这个表是我在带人写图论代码时反复强调的高频问题，基本覆盖了Floyd的新手坑：
| 症状 | 原因 | 修复对策 |
|---|---|---|
| 结果出现大量负数 | INF选成INT_MAX导致加法溢出 | 改用0x3f3f3f3f或INT_MAX/2 |
| 某条短路径没被更新 | k循环没有放在最外层 | 把k循环调到最外层 |
| 对角线d[i][i]变成负数 | 存在负环，或自环初始化为正数 | 检查输入，负环检测 |
| 路径输出不对 | nxt矩阵更新逻辑错误 | 更新时执行nxt[i][j]=nxt[i][k] |
| 无向图对称性破坏 | 只更新了d[i][j]没更新d[j][i] | 对称位置同时更新 |
| 稀疏图运行太慢 | 没有跳过INF的无效迭代 | 在内外层分别加INF判断 |
| 大图超时 | n过大，Floyd本身不适合 | 改用单源堆优化Dijkstra或Johnson算法 |
关于选型，我的经验值是：
- n ≤ 100：随便什么算法都行，Floyd是首选，因为代码最短；
- n ≤ 500：Floyd仍然是舒适区，优化好一点的版本轻松过；
- n ≤ 1000 且图较稀疏：Floyd开始有压力，可以考虑每个点跑一遍堆优化Dijkstra，复杂度 O(n * m log n) 在稀疏图下反而更好；
- n > 10000：绝对不要用Floyd，老老实实分析图的稀疏程度，或者考虑多源信息是否需要全量矩阵，可能根本不需要所有点对，改成按需查询更实际。
最后分享一个小习惯：我写Floyd时一定会先在代码里放一组4节点的小图测试，跟手算结果核对一遍再跑正式数据。这个习惯帮我挡住了不少因为INF设置错误、对称更新遗漏导致的隐蔽Bug。毕竟这个算法虽然短，但一旦某个阶段细节出错，矩阵里全都是看似正常实则错误的值，排错成本反而比长的算法更高。
