直接写，不用那些总结开头。Floyd算法，懂的都懂，多源最短路那个，O(n³)的经典思想。但讲真，网上关于它的文章，九成是贴个伪代码就跑，要么就是拿个教科书模板让你背。真正到了生产环境，或者比赛场上，没人关心你原理背得多熟，关心的是你怎么在最短时间内写出不出错、跑得快的代码。
这篇文章我不打算做那种教科书式复读。我会把Floyd算法的核心思想重新拆一遍，从头推导那个递推式到底在干什么，然后给出我实测下来最顺手、最不容易写错、性能也拉满的C++实现版本。最后还有我踩过的坑和针对具体场景的优化思路。
1. 从动态规划角度重新理解Floyd算法
Floyd算法在数据结构教材里，通常被归类到“图的最短路径”章节，跟Dijkstra和Bellman-Ford放在一起。但很多人学完就忘，根本原因在于：没有真正从动态规划的角度吃透它，而是把它当成一个“三重循环的模板”来背。这个思路是错的，Floyd算法的本质是区间动态规划。
1.1 递推公式的推导与k的含义
定义状态dp[k][i][j]：从顶点i到顶点j，只允许经过编号不超过k的中间节点时，所能达到的最短路径长度。
这里的关键是“允许经过的中间节点编号不超过k”，而不是“一定要经过k”。初次看到这个定义的人，十个有九个会绕进去。举个例子，假设有5个顶点，编号从1到5，dp[3][1][5]表示：从1到5，路上可以经过1号、2号、3号这三个中间顶点（实际上向你爱走不走，但是其他编号更大的顶点，比如4号和5号，不允许作为中间跳板）的最短路。
那么状态转移怎么想？把视角放在第k个中间节点上（也就是新加入的顶点k）：
- 情况一：从i到j的最短路，压根不需要经过顶点k。那dp[k][i][j]就等于dp[k-1][i][j]，跟之前没有顶点k可选时一模一样。
- 情况二：从i到j的最短路，确实经过了顶点k。那路径就可以拆成两段：i到k这一段，和k到j这一段。而这两段路径，因为k是端点，所以它们的中间节点编号都不可能超过k-1。
两段加起来，就是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=1一直枚举到k=n？因为每一轮都在试图引入一个新的“中转枢纽”，看看能不能把某些路径缩短。把维度k从小到大枚举完，dp[n][i][j]就是真正的全源最短路径。
1.2 为什么k必须放在最外层循环
很多初学者会问：三重循环，i、j、k，顺序随便换不都一样吗？
我特别强调：这不是“顺序”问题，这就是Floyd算法的正确性所在。因为dp[k][i][j]依赖的是dp[k-1][...][...]，所以计算第k层的结果时，第k-1层的所有状态必须是已经全部计算出来的。如果k不是最外层，比如把i放最外层，那么内层在算某个(i0, j0)对时，可能会用到尚未计算出来的(i0, k)或(k, j0)在第k-1层的值，结果就错了。
有一种“看起来没错”的写法，就是把三维数组降成二维，直接在原数组上迭代。很多人问：你原地更新，会不会让dp[k][i][j]的更新里，用到已经被第k层“污染”的数据？
答案是：不会。
因为dp[k][i][j]依赖的两个值dp[k-1][i][k]和dp[k-1][k][j]，它们在原地的二维数组里，对应的是dist[i][k]和dist[k][j]。在一轮更新中，第k行和第k列的数据，在这一轮里确实会被更新，但问题是：当我们更新dist[i][j]（i和j都既不是k）时，需要读的dist[i][k]和dist[k][j]，它们的下标都包含k。而dist[i][k]这一格，在从dp[k-1]到dp[k]的递推过程中，依赖的是dist[i][k]（自身不变）和dist[i][k] + dist[k][k]（也是自身），所以它不会因为引入顶点k而变得更短。第k行、第k列天然是第k轮的“不变量”。这就是Floyd可以在原地更新、不需要额外开三维数组的根本原因。
2. 最优C++实现：从零到能跑的完整代码
理论说完，直接上代码。这是我最常用的一套模板，在比赛中、工程里都测试过，兼顾可读性、健壮性和性能。
2.1 基础版本：邻接矩阵 + 三重循环
首先明确一点：Floyd算法的最佳载体是邻接矩阵，因为它需要随机访问任意两点之间的当前最短路。用邻接表存图的话，每次找k的邻居再去更新i到j，反而把复杂度搞成了O(n³)但常数巨大。
#include <bits/stdc++.h> using namespace std; const long long INF = 4e18; void floyd(int n, vector<vector<long long>>& dist) { for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { // 小优化：dist[i][k] 为 INF 就不用继续内层循环了 if (dist[i][k] == INF) continue; for (int j = 0; j < n; ++j) { if (dist[k][j] == INF) continue; long long nd = dist[i][k] + dist[k][j]; if (nd < dist[i][j]) { dist[i][j] = nd; } } } } }几点说明：
- 为什么用long long而不用int？因为最短路长度的累加，有可能超过int的2^31-1范围。尤其是当INF设置为某个很大的值（比如0x3f3f3f3f）时，两个INF一加就直接溢出成负数，整个算法就废了。很多人的Floyd代码在无向图大规模数据下输出负数，十有八九是这里出了问题。
- dist矩阵初始化：对角线dist[i][i]=0，有边的地方填边权，无边的地方填INF。
2.2 性能优化：Cache优化与分支友好
上面那个版本是“正确”的，但在大数据量下还可以再压一压。
先看本质：Floyd的复杂度是O(n³)，n到1000时就要执行10亿次循环。优化空间全是常数级别的，但常数有时就是天壤之别。关键优化点有两个：
第一，把“判断dist[i][k] == INF”和“判断dist[k][j] == INF”这两个if去掉。在CPU层面，连续的数组访问对缓存是友好的，但硬件的分支预测器会对if产生预测开销。如果图比较稠密，绝大多数dist都不是INF，那么两个if的判断大部分时间都是false，预测器很快就会学会“不跳过”，此时if的开销很小。可如果图稀疏，if又可能频繁“跳过”，导致分支预测失败，性能反而更差。
一个折中的方案是：用一个大一点的INF（比如4e18），然后让两个INF相加后溢出成负数，最后判断nd < dist[i][j]时会自然把它过滤掉。但前提是“INF必须足够大，且所有有效的nd都远小于INF”。实际使用中，如果边权总和不可能超过1e18，那这个“让INF自然溢出”的技巧是可行的。只是这样写有点吓人，所以我通常只在比赛时这么干，工程上还是保留if。
第二，循环顺序优化：i和j循环内层交换没有本质区别，但为了更友好的缓存读取，可以让i、j都从小到大遍历，k作为最外层。现代CPU预取器对顺序访问的识别能力很强，这种简单顺序遍历已经足够。
下面是我实测下来比较平衡的版本：
void floyd_fast(int n, vector<vector<long long>>& dist) { for (int k = 0; k < n; ++k) { auto& dist_k = dist[k]; for (int i = 0; i < n; ++i) { long long dik = dist[i][k]; if (dik == INF) continue; auto& dist_i = dist[i]; for (int j = 0; j < n; ++j) { long long nd = dik + dist_k[j]; if (nd < dist_i[j]) { dist_i[j] = nd; } } } } }这里有个很实用的细节：把dist[k]和dist[i]缓存成局部引用dist_k、dist_i。这样可以显著减少二维数组寻址时“每次都要计算基地址 + 行偏移”的开销，也更容易让编译器做向量化优化。实测对n=500以上的图形，能快20%~40%左右。代码量只多了三行，但收益明显。
2.3 路径重建：不只是求最短距离
只求最短距离在很多场景下并不够。如果题目要求输出具体路径，那就需要额外的路径记录数组。常见做法是维护nxt[i][j]表示从i到j的路径上，i的下一个顶点是谁。
void floyd_with_path(int n, vector<vector<long long>>& dist, vector<vector<int>>& nxt) { // 初始化 nxt：如果 i->j 有边，nxt[i][j] = j；否则为 -1 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { nxt[i][j] = (i == j || dist[i][j] == INF) ? -1 : j; } } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { if (dist[i][k] == INF) continue; for (int j = 0; j < n; ++j) { long long nd = dist[i][k] + dist[k][j]; if (nd < dist[i][j]) { dist[i][j] = nd; nxt[i][j] = nxt[i][k]; // 路径经过 k，所以 i 的下一个顶点不变 } } } } } void print_path(const vector<vector<int>>& nxt, int u, int v) { if (nxt[u][v] == -1) { cout << "No path" << endl; return; } cout << u; while (u != v) { u = nxt[u][v]; cout << " -> " << u; } cout << endl; }这个nxt数组很有意思：当更新dist[i][j]时，新路径是i -> ... -> k -> k -> ... -> j，而i到k的下一跳就是nxt[i][k]，所以nxt[i][j]直接赋值为nxt[i][k]。不需要额外记录前驱，因为前驱数组没法在Floyd的原地迭代中维护得这么干净，而后继数组天然配合“从起点开始追踪”的方式。
2.4 负权环检测：Floyd算法的隐藏能力
Bellman-Ford可以检测负权环，Dijkstra不可以。Floyd算法其实也能，只是很多教材没提。思路很简单：跑完Floyd之后，如果存在某个i，使得dist[i][i] < 0，那么图中一定存在负环。
为什么？因为dist[i][i]表示从i出发，经过若干顶点最后回到i的最短回路。如果这个回路长度小于0，那这个回路本身就是一个负权环。反之，如果不存在任何dist[i][i] < 0，那就不存在负环。
注意：如果图中存在负权环，Floyd算法算出的所有dist都不可信，因为路径可以被无限缩短。所以工程上需要在跑完Floyd后立刻检查对角线。
bool has_negative_cycle(int n, const vector<vector<long long>>& dist) { for (int i = 0; i < n; ++i) { if (dist[i][i] < 0) return true; } return false; }这个做法的正确性依赖一个前提：初始化时dist[i][i]=0。如果你不小心把循环图的对角线初始化成了INF，这个检测就会漏报。
3. 关键决策：数据类型、INF设置与矩阵初始化
这一节解决的是“怎么不写错”的问题。我见过太多人在这几个细节上翻车，而且翻车的姿势千奇百怪。
3.1 INF到底该设多大
这是一个极其经典的问题。设小了，真实的最短路可能比INF还大，导致被当成“不存在”；设大了，两个INF相加一溢出不就变成负数了？
在C++里，你用的是int还是long long，直接影响INF的选取。
- int情况：最大值为2^31-1 = 2147483647，INF可取0x3f3f3f3f（约10.6亿）。两个INF相加大约是21.2亿，超过int最大值，会回绕成负数。这就是为什么很多int版Floyd代码里，即使边权很小，也会莫名其妙出现负距离。
- long long情况：最大值为9.22e18，但通常不取到极限。取4e18的话，两个4e18相加会溢出成负数，如果这时候你不做任何if判断直接比较，就会出错。稳妥的做法是用4e18当INF，但在加法前后做好判断，或者选一个“两倍INF也不溢出”的值，比如2e18。我建议：如果图的最短路径下界不会超过1e18，INF取4e18绰绰有余；如果确实有达到1e18量级的数据，就把INF改成2e18并做好加法判断。
最省心的做法是：先估出图中可能出现的最大边权之和上界MAX_DIST，然后设INF = MAX_DIST * 2 + 1，并保证所有有效dist远小于INF。这样两个INF相加会大于任何有效路径但不会溢出（因为MAX_DIST * 4量级远小于long long最大值）。哎，但实际工程里哪有这么完美的估计，多数时候我直接用LLONG_MAX / 4，比如4e18，然后加上“跳过INF”的if判断，又稳又不会溢出。
3.2 无向图与有向图的初始化区别
无向图：dist[i][j] = dist[j][i] = w。注意无向图的邻接矩阵是对称的，Floyd跑完后依然对称。
有向图：只赋值dist[i][j] = w。
自环：dist[i][i]统一初始化为0。如果输入里有负权自环，那么这张图已经有负环了，Floyd跑完对角线会小于0，检测能抓到。
重边：初始化时要取最小值。如果一条边重复给多次，取最小权值即可，否则可能被大权值的边污染。
这里分享一个调试小技巧：在写Floyd前，先单独写一个检查函数，打印出对角线和几个关键点对，确认初始化阶段没有把边读错。很多“算法写对了但答案不对”的情况，其实是建图阶段读边时出了错。
3.3 并发与向量化：Floyd在工程里还能怎么加速
如果你处理的数据量真的很大（比如n超过800），单线程O(n³)在普通机器上可能会卡到1秒以上。这时候有几个方向可以考虑：
利用缓存阻塞（Cache Blocking）：Floyd本质上是矩阵运算，可以切成tile分块做。思路是把k循环拆成若干段，对每一段先加载进L2缓存，再更新所有i、j。这能让内存访问局部性更好。常用分块大小在32~64之间。不过在大多数算法竞赛里没人写，因为太麻烦，效益也不稳定。
利用SIMD向量化：内层循环j是连续内存访问，编译器在-O2 / -O3下有可能自动向量化一部分。上面那个“把dist[i]和dist[k]缓存为引用”的版本，就是在帮编译器更好地做向量化分析。
利用并行：k循环存在依赖关系，每一轮k依赖上一轮k-1的结果，所以不能在k维度之间并行。但i维度的各个行之间互不依赖，可以并行处理。用OpenMP或者std::async都可以。对于n=1000级别，4线程大概能快2.5~3倍。这是性价比最高的并行方式。
void floyd_omp(int n, vector<vector<long long>>& dist) { for (int k = 0; k < n; ++k) { #pragma omp parallel for schedule(static) for (int i = 0; i < n; ++i) { long long dik = dist[i][k]; if (dik == INF) continue; auto& dist_i = dist[i]; auto& dist_k = dist[k]; for (int j = 0; j < n; ++j) { long long nd = dik + dist_k[j]; if (nd < dist_i[j]) { dist_i[j] = nd; } } } } }注意：每个i行的更新是独立的，所以这个并行在逻辑上是安全的。唯一的小心点是需要确定编译器支持OpenMP，并且在编译时加-fopenmp。
4. 常见问题与避坑实战清单
这部分是我长期使用Floyd后总结出的高频事故现场，每一项都对应真实踩过的坑。
4.1 为什么我Floyd跑出来的距离比真实值大
这个多半是最“教科书式”的错误：没有按“先k，再i，再j”的顺序循环。如果i在外层，当i固定时，内层更新用到的dist[i][k]可能还没被这一轮的k循环完整更新过，导致漏掉了一些中转路径。排查方法：把k循环提取到最外层，再跑一遍，对比结果。
另一个原因则是初始化时把不存在的边设成了0。无数人在读图时习惯“dist[i][j] = 0”代表无边，但0在Floyd的语境里意味着“这条边权值为0”。如果存在真正的0权边，就会和“无边”冲突。一定要用INF表示“不可达”。
4.2 为什么答案出现负数
这是最惊悚的错误之一。原因几乎只有一个：INF溢出。用int存距离，INF设成0x3f3f3f3f，然后两个INF一加，溢出成了负数，结果最小路径变成了负的。解法是：换long long，或者像上面说的在加之前判断是否是INF。我偏好在加法前跳过INF，这样等于从源头上防止溢出，然后用一个大INF（4e18）也能保证正常情况不发生溢出。
还有第二种奇怪的负值原因：图中存在负权边但无负环。此时Floyd的结果本身是对的，diagonal距离不会为负。如果某些dist变成了非常负的值，同时又确认没有负边，那大概率还是溢出，而不是负环问题。
4.3 为什么n=500时跑得很慢
如果确认复杂度是O(n³)且n=500，理论上大约1.25亿次操作，C++在普通机器上应该在0.1秒级别。如果跑得很慢，看看是不是用了vector<vector >但又没有加优化编译选项，或者是在debug模式下运行。debug模式下vector的访问会带边界检查，速度慢十倍都不奇怪。
另一个隐藏性能瓶颈是：vector<vector<...>>本身不是一块连续内存。每一行是一个独立的动态数组，行与行之间的地址不一定相邻。内层j访问dist[i][j]时，跨行访问会造成缓存不友好。如果想追求极致的性能，可以申请一个一维数组，把二维矩阵在逻辑上映射到一维：
long long* dist = new long long[n * n]; auto get = [&](int i, int j) -> long long& { return dist[i * n + j]; };这个版本对缓存的友好度更高，但没有vector 那么好写。看你的用途：如果只是算法教学或者一般规模，vector 完全够用；如果数据规模大、要求时间卡得严，就用一维映射方案。
4.4 为什么我的路径重建输出不对
主要两类问题。
第一，nxt数组初始化错了。很多人把nxt初始化为i，表示“默认下一跳是自己”，这会在无路径时输出一个自环。正确做法是：初始化为-1表示不存在，只有有边时才是j。
第二，路径更新时用错了nxt。我之前写的是nxt[i][j] = nxt[i][k]。有人会写成nxt[i][j] = nxt[k][j]或者别的，输出路径时就会莫名其妙地跳到奇怪的点上。建议输出路径时打印每一步，看是不是在某个中转点卡住了。如果nxt[i][j]指向了一个中间点x，再打印nxt[x][j]，一路推到j为止。
4.5 稀疏图别用Floyd：什么时候该换算法
Floyd是O(n³)，Dijkstra堆优化是O(mlogn)。如果n很大但m很小（稀疏图），或者只需要求单源最短路，Floyd就不划算了。
一般经验是：
- n <= 400，Floyd 稳。
- 400 < n <= 800，Floyd 可接受，但需要优化常数。
- n > 1000 且图比较稀疏，建议用 n 次 Dijkstra 而不是 Floyd。
换个角度思考：Floyd的优势是代码短、实现简单、全源信息一次算完，而且天然支持负权边。如果业务场景是多源查询多次、图不算特别大、可能有负权但无负环，Floyd就是最佳的。
4.6 传递闭包：Floyd思想的另一个形态
Floyd不仅能算最短路，还能算可达性。只要把“加法”改成“逻辑或”，把“取最小”改成“逻辑与”，三重循环的骨架不变，就能求出任意两点之间是否存在路径。这在关系图谱、状态可达性分析里非常常用。
void transitive_closure(int n, vector<vector<bool>>& reach) { 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]; }这个版本的位运算还可以用bitset优化，把内层循环通过bitset的按位或一次性做完。对n=2000来说，bitset版本会比布尔矩阵快非常多，这也是很多图论库内置的实现方式。跑一轮下来你会发现，Floyd的“三重循环”真的像个万能框架，业务形态变化，运算符变化，但思想不变。
5. 实战案例：从输入到输出的完整推演
为了把这套东西串起来，我用一个具体、无歧义的示例来走一遍完整流程。假设有4个城市，编号0到3，道路如下（有向）：
0 -> 1，边权 3
0 -> 3，边权 7
1 -> 0，边权 2
1 -> 2，边权 6
2 -> 0，边权 5
2 -> 3，边权 1
3 -> 2，边权 9
初始邻接矩阵：
| 从\到 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 3 | INF | 7 |
| 1 | 2 | 0 | 6 | INF |
| 2 | 5 | INF | 0 | 1 |
| 3 | INF | INF | 9 | 0 |
k=0时，以0号点为中转。逐个检查(i, j)，看看走0能不能更短。比如i=3, j=3，dist[3][0]=INF，跳过；i=1, j=1，dist[1][0]+dist[0][1]=2+3=5，但dist[1][1]=0，不更新。i=1, j=3，dist[1][0]+dist[0][3]=2+7=9，dist[1][3]=INF，所以更新为9。这一轮结束后，部分d变大。
k=1时，以1号点为中转。i=0, j=2，dist[0][1]+dist[1][2]=3+6=9，dist[0][2]=INF，更新为9。i=0, j=3，dist[0][1]+dist[1][3]=3+9=12，比现有dist[0][3]=7大，不更新。i=2, j=2不动，i=2, j=1，dist[2][1]暂时还是INF，无法中转。
k=2时，以2号点为中转。i=0, j=3，dist[0][2]+dist[2][3]=9+1=10，比现有7大，不更新。i=3, j=0，dist[3][2]+dist[2][0]=9+5=14，dist[3][0]=INF，更新为14。
k=3时，以3号点为中转。i=2, j=1，dist[2][3]+dist[3][1]=1+INF=INF，无法中转。i=1, j=3，由于dist[1][3]=9，dist[3][...] 无法提供更短。
最终得到：
| 从\到 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 3 | 9 | 7 |
| 1 | 2 | 0 | 6 | 9 |
| 2 | 5 | INF | 0 | 1 |
| 3 | 14 | INF | 9 | 0 |
注意2 -> 1仍不可达。这是因为从2出发，经过3再经过1，实际是2->3(1)，3->2(9)加上2->... 绕回1，在图上死循环路径，却绕不出来。这是有向图的正常结果。跑Floyd前一定确认图是有向还是无向，不要想当然。
6. 三个容易被忽略的优化细节
把上面那些内容浓缩成三个最常被忽略、但收益极高的细节：
一是“跳过INF”的判断不要省。虽然会增加分支预测开销，但能防止溢出、能减少大量无意义加法运算，对稀疏图收益尤其明显。如果是稠密图，建议在编译期把代码拆成两个版本，一个带判断，一个不带，用宏或if constexpr控制。
二是“数组内存连续性”。如果有性能瓶颈，用一维数组映射替代vector ，可能会获得远超预期的提升。这是因为二维vector的每一行独立分配内存，行与行可能不连续，cache miss会非常严重。当你需要频繁按行访问时，一维映射的优势会被放大。
三是“循环内把dist_k引用缓存”。哪怕只是加一行auto& dist_k = dist[k]，也能让编译器更好地将内层循环向量化。不要小看这种“本地引用”，在热点循环里，它减少的数组寻址开销会被放大到几十倍。
7. 实战体会与经验补充
我最早学Floyd时，只顾着背模板，以为三重循环就是全部。直到有次在项目里要计算几百个节点之间的最短路径，顺手用了Floyd，发现运行时间完全不可接受，才开始排查各种优化。后来我换用堆优化Dijkstra跑n次，时间降下来了，但代码复杂度一下子上去了。再后来，我意识到问题的本质是：图结构是稠密还是稀疏？有多少个源点？允许负权吗？把这两个问题想清楚，算法选择就不纠结了。
我个人现在的习惯是：数据量小（n <= 500）时无脑Floyd；n在500到1000之间，先看邻接矩阵是否已经存在，如果存在就继续Floyd，配合上面的优化；n超过1000且图是稀疏的，老老实实跑n次堆优化Dijkstra。至于有负权边又无负环的情况，Floyd依然是最安心的选择，因为Dijkstra不能处理负权，Bellman-Ford的代码写起来又啰嗦。
最后分享一个压箱底的小技巧：在跑Floyd前，先用质数法或随机权值生成小规模的图，写一个暴力BFS/DFS版本验证Floyd结果。任何一个边权为1到100、点数不超过8的随机图，暴力验证和Floyd的结果必须完全一致。这不是浪费时间，这是培养“算法直觉”最有效的方式。等你亲手写上百次Floyd之后，你可能会像我一样，逐渐能“看见”那个三维状态在矩阵里流动的过程——那时候，这算法才是真正长在你脑子里的。
