算法基础篇写到第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定义成0x3f3f3f3fINF加一个负数会小于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时同步更新nxtif 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边权20到2边权71到2边权31到3边权102到3边权1。初始dist矩阵从\到01230027INF1INF03102INFINF013INFINFINF0当k1时允许0、1作为中转点。0到2会从7更新成0到1的2加1到2的3得50到3也会从无穷大更新成0到1的2加1到3的10得12。这时候矩阵里0到2已经变成更短的5但0到3还不是最优因为0到3的最优路径还需要经过2。当k2时允许0、1、2作为中转点。这时0到3可以用已经更新好的0到2的5加上2到3的1变成61到3也能从10更新成1到2的3加2到3的1变成4。最终矩阵从\到0123002561INF0342INFINF013INFINFINF0这个过程很清晰地展示了Floyd“逐轮开放中转点”的更新节奏。一开始0到3只知道走直接边结果不可达k1时走0-1-3有了初步路径k2时才通过0-1-2-3这条更长组合拿到最终答案。如果没有k2这一步0到3就会停在12这个非最优值上可见外层k推进到哪个阶段矩阵就记录哪个阶段的信息。4. 复杂度、适用场景与算法的横向对比搞清楚代码之后还得知道Floyd什么情况下该用、什么情况下不该用以及和其他算法怎么配合。4.1 时间复杂度与空间复杂度分析Floyd的时间复杂度是O(n^3)空间复杂度是O(n^2)。这个复杂度跟边数无关所以它不怕稠密图。n200时总共800万次基本操作Python也能很快跑完n500时是1.25亿次C大概不到1秒Python用PyPy可能也要好几秒n1000时到10亿次量级普通单机基本别想了。所以我的经验是最短路场景下n在300附近都能放心用Floydn到500以上就要掂量一下常数和语言传递闭包场景可以用bitset优化复杂度降到n^3/64左右n能放宽很多。空间上是两个n乘n矩阵dist和nxt。n1000时每个int矩阵约4MB两个8MB内存压力不大。如果只求可达性还可以用位压缩把每行压成一个bitset空间和速度都能进一步优化。优化之后传递闭包的n可以放到2000甚至更大这在很多关系判断类题目里非常实用。4.2 Floyd、Dijkstra、Bellman-Ford怎么选简单整理一张表方便对照算法求解类型时间复杂度负权边负环检测适用场景Dijkstra堆优化单源O(m log n)不支持否非负权稀疏图/稠密图均可Bellman-Ford单源O(nm)支持能边数少的带负权图SPFA单源平均O(km)最坏O(nm)支持能一般带负权图常数小Floyd全源O(n^3)支持能n小、稠密图、要求全源Johnson全源O(nm log n)支持能稀疏大图的全源最短路选型口诀很简单单源非负权优先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手到擒来传递闭包、最小环、动态加点这类变体题也能一眼看穿思路。这个收获比单纯记住一段三重循环值钱得多。