Floyd算法详解：动态规划实现全源最短路径与常见坑位

算法基础篇写到第11篇，今天聊Floyd算法。很多刷题的朋友一开始接触最短路时，通常先学Dijkstra，等遇到多源最短路或者带负权边的图时才意识到，Floyd这套方案有多省心。Floyd-Warshall算法是一套基于动态规划的全源最短路径算法，核心代码只有几行，却能一次性求出任意两点之间的最短距离，在稠密图、小数据范围、以及需要路径重构的场景下相当能打。这篇文章我会从为什么需要它、动态规划细节、代码实现、常见坑位几个层面把Floyd讲透。不管你是准备蓝桥杯、力扣还是算法面试，只要把这一篇吃透，Floyd基本不会丢分。

1. 为什么需要Floyd算法：多源最短路的痛点

最短路算法家族里，Dijkstra是单源算法，一次只能从一个起点出发，算出到所有其他点的最短距离。如果题目只问一个起点，Dijkstra当然是最优选；但题目一旦变成“求任意两点间的最短路”，比如城市群里任意两个城市之间的最短驾车距离，用Dijkstra就得跑n次，每次还要维护堆优化逻辑，代码量、出错概率一起上升。Floyd处理的就是这种全源最短路问题，时间复杂度固定为O(n^3)，对n在几百以内的图来说，往往是最省心的正解。

我见过不少初学者觉得Floyd代码太短、看起来“没技术含量”，就跳过不学，这是很吃亏的。蓝桥杯、力扣、PAT、ACM模板里Floyd都是高频基础算法。更重要的是，Floyd能处理带负权边的图（只要没有负环），这一点Dijkstra做不到。下面从算法分工和设计思路入手，把Floyd掰开揉碎讲清楚。

1.1 单源与全源：算法的分工

单源最短路算法里最常用的两个代表：Dijkstra时间复杂度O(m log n)，要求边权非负；Bellman-Ford时间复杂度O(nm)，允许负权边但速度慢，还能检测负环。它们都有一个共同限制：一次只能求一个起点到所有点的距离。要求全源最短路，最简单的思路就是把这些单源算法重复跑n次，每个点都当一次起点。但这样做的问题是，如果图比较稠密，边数m接近n方，总复杂度会变成O(n^2 log n)量级甚至更高，代码写起来也繁琐。

Floyd走的是另一条路：它不关注“从谁出发”，而是直接维护一个n乘n的距离矩阵，第[i][j]项表示从i到j当前已知的最短距离。每一次迭代，它都尝试让更多节点成为“中转站”，最终矩阵里的每一项就是全源最短路径。另一个全源算法Johnson用势能转换负权边再跑n次Dijkstra，适合稀疏大图，但编码复杂度高，刷题和面试中很少用到。相比之下，Floyd是“无脑、稳定、好调”的全源方案，尤其适合稠密图和小数据范围。用一句话类比：单源算法像只查一个出发地的列车时刻表，全源算法则把任意两站之间的最优路线全部算好，直接查表。Floyd做的就是这张表。

1.2 Floyd的核心设计思路

Floyd的核心松弛操作只有一行：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。意思是，从i到j，如果先到k、再由k到j，总距离比当前已知的短，就用这条更短的路径替换。外层循环k从0到n-1依次增加，相当于每次开放一个编号为k的节点作为允许中转的节点。这样经过n轮迭代后，所有节点都允许作为中转点，矩阵里的值就是真实最短距离。

很多资料把Floyd说成“暴力枚举”，其实它比暴力聪明得多。纯暴力枚举任意两点间所有可能路径是指数级的，而Floyd用动态规划把问题拆成了n个阶段，每个阶段只做一个简单决策：“经过新开放的中转点k，能不能更短？”能就更新，不能就保持。这个思想和你日常规划路线很接近：如果知道从A到B有一条老路，又发现从A到C加C到B的组合更近，自然会把这条新组合记下来，下次规划更长路线时再用它。理解了“中转点集合逐步扩大”这个核心，后面所有细节就都顺理成章了，包括三重循环为什么k必须在外层、路径重构怎么做、为什么Floyd能求最小环。接下来我详细拆解它的动态规划本质。

2. 动态规划的本质：状态定义与转移方程

很多教程会把Floyd直接当成“三重循环模板”来背，结果换个问法就不会了。真正理解Floyd，要从它的状态定义开始。

2.1 状态定义：从“允许经过”说起

严格来说，Floyd的状态可以写成三维：dp[k][i][j]表示从i到j，只允许经过编号不超过k的节点作为中转点时，最短路径的长度。这里“允许经过”是动态规划阶段的关键。最开始还没有开放任何中转点时，dp[0][i][j]就是邻接矩阵里的直接边权；i到j如果没有直接边，就是无穷大，i到i则永远是0。

当开放编号为k的节点时，从i到j的最短路径只可能有两种情况：第一种根本不经过k，那么dp[k][i][j]和dp[k-1][i][j]一样；第二种路径经过k，就可以拆成两段：i先到k、k再到j，而这两段各自只允许经过编号小于k的节点，所以是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])

这个方程本质上是在说：每个新阶段，要么沿用旧路径，要么用两个已求好的子路径拼出新的完整路径。等到所有节点都开放完，dp[n][i][j]就是真正的全源最短路径。

为什么实际代码里能省掉第一维只用二维数组？因为第k层只依赖第k-1层，而且更新dist[i][j]时用到的dist[i][k]和dist[k][j]在第k轮里不会被自己破坏。原因也很简单：dist[i][k]的终点是k，如果在第k轮里把k当中转点，那路径就变成i先到k，再经k到k，绕了一个无意义的小圈，不可能更短，所以dist[i][k]不会因这轮更新而改变；dist[k][j]同理。因此原地滚动更新是安全的，这也是Floyd代码能短到这个程度的原因。

2.2 转移方程与三重循环顺序

有了状态和转移，代码自然是三重循环：

for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

外层k表示“当前允许作为中转点的节点编号上限”，内层i、j枚举所有起点和终点。每完成一轮k，矩阵里所有dist[i][j]都会更新成“允许经过前k个节点”时对应的最短距离。n轮之后，全源答案就齐了。

写代码时我习惯在更新前判断一下dist[i][k]和dist[k][j]是不是无穷大。这样有两个好处：一是避免无意义的加法运算，二是防止无穷大加负权边变成一个“假数字”。比如C++里如果把INF定义成0x3f3f3f3f，INF加一个负数会小于INF，如果不加判断，某个不可达的点对可能被错误地当成可达，这个小坑在带负权图里尤其致命。

2.3 为什么k必须在外层

这是Floyd最容易踩的坑。很多人会想，反正dist矩阵一直在更新，为什么不能把k放在最内层？原因在于Floyd是分阶段动态规划，外层k一定要代表“当前允许中转的节点集合”，内层i、j更新完整个矩阵后，才能进入下一阶段。如果k在最内层，处理某一个(i,j)点对时，dist[i][k]和dist[k][j]可能还没有充分完成“只允许使用前k-1个中转点”的迭代，也可能已经混入了更大编号的中转点，DP状态的阶段性就乱了，最终矩阵可能在某些特殊图上给出错误结果。

更麻烦的是，顺序写错后小数据常常碰巧能跑对，因为图简单时路径组合少，怎么试都能蒙对；数据一大、路径结构复杂，错误就暴露出来了，而且非常难debug。我的建议是：老老实实把k固定在最外层，把它当成铁律，别在比赛现场尝试“优化成别的顺序”。真想验证这个坑，可以用随机生成的小图和暴力全排列路径对比，结果会告诉你顺序的重要性。

3. 手把手实现Floyd：初始化、迭代与路径重构

理论讲完，下面进入能直接拿去用的实操环节。我按初始化、核心代码、路径重构、完整示例四步展开。

3.1 邻接矩阵初始化与INF选值

Floyd是基于邻接矩阵的算法，第一步是把矩阵铺好。所有dist[i][i]初始化为0，表示自己到自己距离为0；没有直接边的点对初始化为无穷大；有直接边的按边权填入。如果有重边，保留最小的那条；如果是无向图，记得把dist[u][v]和dist[v][u]都填上。

INF的选值是一个容易被忽略但很关键的细节。C++里定义INF最好不要用INT_MAX，因为两个INT_MAX相加会直接溢出成负数，更新条件永远触发，程序立刻错乱。我常用的int类型INF是0x3f3f3f3f，这个数大约10.6亿，两个相加约21.2亿，仍然小于int上界，安全且足够大。配合memset(dist, 0x3f, sizeof(dist))，初始化一整个矩阵非常方便。用long long时，可以把INF设为0x3f3f3f3f3f3f3f3f。Java里我更习惯用Integer.MAX_VALUE / 2，或者直接用Long.MAX_VALUE的开平方级别的大数。Python最省事，直接用float('inf')，加法不会溢出，判断也直观。

3.2 核心代码：Python/C++/Java实现

先给一份可运行的Python版本，注释比较全：

import sys def solve(): data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) m = int(next(it)) INF = float('inf') dist = [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for _ in range(m): u = int(next(it)) v = int(next(it)) w = int(next(it)) dist[u][v] = min(dist[u][v], w) # 如果是无向图，再加一行：dist[v][u] = min(dist[v][u], w) for k in range(n): for i in range(n): if dist[i][k] == INF: continue for j in range(n): if dist[k][j] == INF: continue nd = dist[i][k] + dist[k][j] if nd < dist[i][j]: dist[i][j] = nd # 输出或处理dist矩阵 for i in range(n): print(" ".join(str(int(dist[i][j])) if dist[i][j] != INF else "INF" for j in range(n))) if __name__ == "__main__": solve()

C++版本是竞赛常用姿势：

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int dist[505][505]; int main() { int n, m; scanf("%d%d", &n, &m); memset(dist, 0x3f, sizeof(dist)); for (int i = 0; i < n; ++i) dist[i][i] = 0; while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dist[u][v] = min(dist[u][v], w); // dist[v][u] = min(dist[v][u], w); // 无向图 } for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; return 0; }

Java版本结构完全一样，用long或int数组，INF用Integer.MAX_VALUE / 2，三层循环照写就行。需要提醒的是，Java创建二维数组时逐行初始化比一次性填充快一些，n到500以上时也能感觉到差别。我的建议是：把其中一种语言版本做成自己的模板，反复敲熟，考场上直接默写，不占用思考时间。

这里分享一个实测有效的性能小技巧：在Python内层循环里，先把dist[i][k]取到局部变量，比如nd = dist[i][k]，然后内层循环统一用nd + dist[k][j]来比较。这样能省掉大量二维数组寻址，n到300左右时提速明显。C++编译器可能自动优化，但手动写成局部变量也没坏处。

3.3 路径重构：记录中间点

如果题目只要求距离，上面的代码已经够了。但很多题会要求输出具体路径，这时候需要额外开一个后继矩阵nxt。初始化时，nxt[i][j] = j，表示当前认为从i到j的第一步是直接走到j。更新dist时同步更新nxt：

if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] nxt[i][j] = nxt[i][k]

这里为什么是nxt[i][j] = nxt[i][k]，而不是nxt[i][j] = k？因为nxt[i][k]表示从i到k的路径上第一个节点，而完整路径是“i到k的某段路径 + k到j”，所以从i出发的第一步，应该沿用i到k路径的第一步。这样记录之后，打印路径只需要循环：

def print_path(i, j): if dist[i][j] == INF: print("No path") return res = [] u = i while u != j: res.append(u) u = nxt[u][j] res.append(j) print(" -> ".join(map(str, res)))

注意：nxt[i][i]在初始化时最好置为-1，打印起点等于终点时直接返回，避免while循环里自己指向自己造成死循环。这是路径重构最容易翻车的地方。另外，不要在全部算完后用dist[i][k] + dist[k][j] == dist[i][j]反推路径，因为满足等式的中间点可能不止一个，你选到的那个不一定能构成连通路径，容易出现死循环或乱序路径。

3.4 完整示例：跑一遍看看

用一个4节点有向图验证。假设边：0到1边权2，0到2边权7，1到2边权3，1到3边权10，2到3边权1。

初始dist矩阵：

当k=1时，允许0、1作为中转点。0到2会从7更新成0到1的2加1到2的3，得5；0到3也会从无穷大更新成0到1的2加1到3的10，得12。这时候矩阵里0到2已经变成更短的5，但0到3还不是最优，因为0到3的最优路径还需要经过2。

当k=2时，允许0、1、2作为中转点。这时0到3可以用已经更新好的0到2的5，加上2到3的1，变成6；1到3也能从10更新成1到2的3加2到3的1，变成4。最终矩阵：

这个过程很清晰地展示了Floyd“逐轮开放中转点”的更新节奏。一开始0到3只知道走直接边，结果不可达；k=1时走0-1-3有了初步路径；k=2时才通过0-1-2-3这条更长组合拿到最终答案。如果没有k=2这一步，0到3就会停在12这个非最优值上，可见外层k推进到哪个阶段，矩阵就记录哪个阶段的信息。

4. 复杂度、适用场景与算法的横向对比

搞清楚代码之后，还得知道Floyd什么情况下该用、什么情况下不该用，以及和其他算法怎么配合。

4.1 时间复杂度与空间复杂度分析

Floyd的时间复杂度是O(n^3)，空间复杂度是O(n^2)。这个复杂度跟边数无关，所以它不怕稠密图。n=200时，总共800万次基本操作，Python也能很快跑完；n=500时是1.25亿次，C++大概不到1秒，Python用PyPy可能也要好几秒；n=1000时到10亿次量级，普通单机基本别想了。所以我的经验是：最短路场景下，n在300附近都能放心用Floyd，n到500以上就要掂量一下常数和语言；传递闭包场景可以用bitset优化，复杂度降到n^3/64左右，n能放宽很多。

空间上是两个n乘n矩阵：dist和nxt。n=1000时每个int矩阵约4MB，两个8MB，内存压力不大。如果只求可达性，还可以用位压缩，把每行压成一个bitset，空间和速度都能进一步优化。优化之后，传递闭包的n可以放到2000甚至更大，这在很多关系判断类题目里非常实用。

4.2 Floyd、Dijkstra、Bellman-Ford怎么选

简单整理一张表，方便对照：

选型口诀很简单：单源非负权优先Dijkstra；单源有负权用Bellman-Ford或SPFA；多源且n小，直接Floyd；多源且图很大很稀疏，才考虑Johnson。实际刷题里，Johnson出现频率很低，Floyd反而是高频货，因为很多题目数据范围就是给Floyd准备的。做多了你会发现，算法选型不是越高级越好，而是越贴合数据范围越好。

4.3 典型应用场景：传递闭包与最小环

Floyd的变体特别多，这里挑两个最常见的展开。

第一个是传递闭包。把dist[i][j]当成布尔值：有边为true，无边为false，自己到自己为true。然后转移方程改成reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])。这样跑完就能判断任意两点之间是否存在一条路径，而不关心路径长度。很多“可达性”题目，比如社交关系传递、课程依赖关系判断，本质上都是传递闭包问题。用bool数组能写，n再大一点可以用bitset加速，把内层j循环压成按位或操作。

第二个是求无向图的最小环。Floyd可以在算最短路的同时求最小环长度。关键技巧是：在第k轮更新dist之前，枚举所有i小于j且都小于k的点对，用dist[i][j]加上原图中i到k的边权、k到j的边权，尝试更新答案。为什么必须在更新前做？因为此时dist[i][j]还是“只允许经过编号小于k的节点”的最短路径，这样dist[i][j]和两条直接边拼起来就构成一个经过k且不重复的最小环，不会出现绕圈重复的情况。如果放到更新后，dist[i][j]可能已经经过k，拼出来就不是环而是重复路径了。核心思路记住：“先查环，再更新”。

5. 常见错误与排查技巧实录

下面这些坑，我基本都在真实刷题和给别人review代码时遇到过，逐条写出来，希望能帮大家省排查时间。

5.1 三重循环顺序写错的后果

前面讲了k必须在外层，这里再强调一遍症状和排查方式。顺序错误的代码，小数据可能跑得对，但一旦出现一条需要多个中转点组合的路径，结果就可能偏大或者偏小。偏大是因为某些路径组合根本没被尝试到；偏小则可能因为用了还没完全迭代的中间结果。排查时我会写一个暴力函数，用DFS或者枚举所有点排列去求真实最短路，然后把Floyd结果和暴力结果对比，专门用随机小图多测几轮。一旦发现不一致，几乎都是循环顺序问题。把k挪回最外层，问题消失。

5.2 INF溢出与精度问题

这是C++最常见的坑。INF定义为INT_MAX，两个相加会溢出成负数，于是dist[i][j]被错误更新成很小的负值，整个矩阵不可信。解决办法是用0x3f3f3f3f这类“两倍仍安全”的大数。Java里用Integer.MAX_VALUE/2也是同理，确保加法不越界。浮点边权更要注意：INF用1e30之类的足够大数字，比较时留一个eps，避免浮点误差导致更新一直抖。处理带负权图时，我强烈建议在循环里加上“跳过INF”的判断，防止INF加一个负数小于INF的假连通问题。这属于初始化细节，但不注意就是整场AC变WA的惨案。

5.3 负权环的判断

Floyd跑完后，如果存在dist[i][i] < 0，说明图里有负权环，因为从i出发绕一圈还能回到i且总权为负，最短路长度就失去了下界。这里要特别注意：有负权环的图上，Floyd的最终矩阵不是正确答案，但它能帮你检测出环的存在。如果题目明确说没有负环，直接算就行；如果没给保证，跑完扫一遍对角线，负了就说明数据有问题，或者要改用其他思路。还有一种情况是初始就有负权自环，比如dist[i][i]填进去就是负数，这本身也算负环。

5.4 路径重构遇坑

路径重构有几种常见错误。一是初始化nxt[i][i]没处理，打印路径时可能从0一直走到0，看似结束不了；二是更新nxt时写成了nxt[i][j] = k，导致打印路径时跳转逻辑混乱，输出直接错乱；三是在输出阶段用距离相等反推中间点，结果选了一个不连通的k。我的建议非常明确：用后继矩阵法，nxt[i][j]记录“i到j路径上i的下一个节点”，初始化nxt[i][j]=j，自环设成-1，更新dist时同步更新nxt[i][j] = nxt[i][k]。打印时用一个简单的while循环，配合一个访问计数器防止异常死循环，基本上就不会出错。

5.5 在线评测中的实测心得

实际比赛里用Floyd，我一般会做三件事。第一，确认数据范围。n是否在几百以内，有没有负权边，图是有向还是无向。第二，输入优化。Python用sys.stdin.buffer.read().split()统一读进来再迭代，C++用scanf或者自定义快读，Java用BufferedReader，避免IO成为瓶颈。第三，把模板代码写到极致简洁，不引入多余判断。蓝桥杯和力扣的图论题，n往往就给得很小，Floyd几乎可以无脑套。唯一要注意的是重边和自环，初始化时别用赋值，用min覆盖；自环边权如果不是负数，最好忽略掉，因为dist[i][i]理应是0。

6. 从Floyd到图论题：我的模板与练习建议

最后分享一点个人使用习惯和练习路线，都是踩过坑之后总结出来的。

6.1 我私藏的Floyd模板与使用习惯

我自己的Floyd模板长这样：初始化矩阵用INF和0；读边时处理重边、无向图；主循环里k、i、j三层，判断跳过INF；需要路径时同步维护nxt。代码保持极简，因为越简越不容易写错。实际做题时，我判断用不用Floyd有个偷懒标准：只要题目求的是“所有点对之间的最短距离”、“任意两点是否可达”、“最小环”，并且n不超过300，无脑写Floyd，不考虑其他算法。省下来的时间可以用来调试或者推后面的题。在带负权的数据里，我还会额外跑一遍对角线检查负环，防止题目数据里有隐藏的边界情况。

6.2 适合巩固的练习题推荐

如果只看不练，Floyd很快会忘。建议按顺序做几道题巩固：力扣1334“阈值距离内邻居最少的城市”是最典型的全源最短路应用，先用Floyd算出所有点对距离，再统计每个城市在阈值范围内的邻居数，逻辑清晰；洛谷P1119“灾后重建”是Floyd的进阶变体，村庄按时间顺序恢复通车，相当于Floyd外层k动态推进的过程，做一遍能极大加深对“中间点逐步开放”的理解；蓝桥杯往年题里也有不少多源最短路题目，拿来练手很合适。做完这些，Floyd基本就焊在脑子里了。

我个人在实际操作中的体会是：Floyd的代码短到只有几行，但它真正的难点不在“背代码”，而在理解“k”这个维度。哪天真把“k是中间点集的阶段推进”这个观念内化了，你会发现不仅Floyd手到擒来，传递闭包、最小环、动态加点这类变体题也能一眼看穿思路。这个收获，比单纯记住一段三重循环值钱得多。