先别急着背模板。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里习惯用vectorvectorint但如果追求极致性能后续章节会讲到一维平铺。初始化矩阵时原题目里没有的边要填一个“无穷大”不能填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 longINF 取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(vectorvectorint 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 距离 30 - 3 距离 71 - 2 距离 21 - 3 距离 12 - 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] 5d[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 行之间互不依赖数据竞争只存在于同一行的不同元素所以并行是安全的。不过在绝大多数业务代码和课程项目中这种微优化不是瓶颈最重要的还是代码清晰和正确。我自己的习惯是平时用vectorvectorint基础版只有在 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 longINF取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]; }重建路径时vectorint reconstruct_path(int u, int v, vectorvectorint nxt) { if (nxt[u][v] -1) return {}; // 不可达 vectorint 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算法思想上的变体非常多最常用的两个是传递闭包和最小环。传递闭包解决的是“可达性”问题也就是判断任意两点之间是否存在路径不管路径多长。这时可以把距离矩阵替换成布尔矩阵vectorvectorbool reach(n, vectorbool(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是动态更新的最短路径矩阵。为什么必须在更新之前枚举因为如果先更新了dd[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 ≤ 500Floyd仍然是舒适区优化好一点的版本轻松过n ≤ 1000 且图较稀疏Floyd开始有压力可以考虑每个点跑一遍堆优化Dijkstra复杂度 O(n * m log n) 在稀疏图下反而更好n 10000绝对不要用Floyd老老实实分析图的稀疏程度或者考虑多源信息是否需要全量矩阵可能根本不需要所有点对改成按需查询更实际。最后分享一个小习惯我写Floyd时一定会先在代码里放一组4节点的小图测试跟手算结果核对一遍再跑正式数据。这个习惯帮我挡住了不少因为INF设置错误、对称更新遗漏导致的隐蔽Bug。毕竟这个算法虽然短但一旦某个阶段细节出错矩阵里全都是看似正常实则错误的值排错成本反而比长的算法更高。