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

图论里有一类问题看起来简单做起来却很容易让人绕晕——求所有点对之间的最短路径。我第一次真正把floyd()算法用明白是在一次模拟网络拓扑的练习题里一张图有几十个节点要求把每两个路由节点之间的最优路径都算出来并且要能处理负权边。当时我第一反应是跑n遍Dijkstra结果写出来的代码又长又难调后来换成floyd()一个三重循环全搞定代码不到二十行。这篇文章就把我对这个算法的理解、踩过的坑、以及实际使用时的细节一次性讲清楚。floyd()算法也叫Floyd-Warshall算法专门用来求带权图有向或无向中所有节点对之间的最短路径长度。它最大的特点是实现简单、思路直观适合节点数量几百以内的稠密图也是很多图论题目的基础工具。无论你是正在备考算法面试的学生还是实际工作中需要处理最短路计算的开发者这篇文章都值得从头看到尾——尤其是后面关于循环顺序和INF取值的部分网上很多博客都没说透。1. 先搞清楚floyd()到底解决什么问题很多教材一上来就甩状态转移方程但如果你不知道这个算法出生的背景很容易陷入背公式的误区。我觉得有必要先把问题本身讲透floyd()到底在解决哪一类问题它和单源最短路算法之间的边界在哪里。1.1 从单源最短路到全源最短路的跳跃先复习一个基础概念单源最短路就是指定一个起点s求s到其他所有点的最短路径。Dijkstra算法和Bellman-Ford算法解决的都是这个问题。它们输入一个起点输出一个一维数组dist[]dist[i]表示从s到i的最短距离。现在把问题升级一下如果我要知道图中任意两个点之间的最短距离怎么办比如一张地图上有5个城市我要算任意两座城市之间的最短里程或者一个社交网络里我要算任意两个人之间最少隔着几层关系。这就是全源最短路All-Pairs Shortest Path, APSP。floyd()算法解决的就是这个问题。它的输入是一个邻接矩阵或者边列表转成邻接矩阵输出是一个二维矩阵d[][]其中d[i][j]就是节点i到节点j的最短路径长度。可能需要花点力气理解的地方在于这种问题为什么值得单独设计一个算法而不是简简单单调用n次单源最短路就行。我后面会详细分析这里先记住floyd的核心定位它是专门为小规模全源最短路设计的、基于动态规划思想的最直白解法。1.2 为什么不用Dijkstra跑n遍这是我最常被问到的问题。从时间复杂度上看Dijkstra用二叉堆优化后是O((VE)logV)跑n遍就是O(V(VE)logV)。在稀疏图里E接近V这个复杂度可能只有O(V²logV)看起来确实不错。但有几个实际问题第一Dijkstra处理不了负权边。只要图里有一条负权边Dijkstra的正确性就崩了。你可能会说那我可以改用Bellman-Ford跑n遍复杂度O(V²E)在稠密图里是O(V⁴)非常难看。而floyd()算法天然支持负权边只要不存在负权回路它都能求出正确结果。第二实现复杂度完全不同。Dijkstra跑n遍你得写堆优化、写松弛、处理多轮初始化bug率相当高。而floyd()的三重循环几乎不可能写错除非循环顺序错了这个我后面会重点讲一行转移方程走天下。第三稠密图里的实际表现。当E接近V²时Dijkstra跑n遍的复杂度是O(V³logV)反而不如floyd()的O(V³)注意常数因子和logV的差距。所以如果你面对的是一张节点规模不大比如V≤500的稠密图floyd()几乎是默认选择。我给一个实际经验很多算法题里看到V≤300、V≤500这个数据范围考点基本就在引导你使用O(V³)的floyd。如果V到了1000以上那十有八九这道题的正解不是floyd你要重新考虑用Dijkstra或者Johnson算法。2. 核心原理一次搞懂三重循环的动态规划这一节是整个算法的灵魂。我见过太多人把floyd的三重循环背下来了但完全说不清为什么这么写结果一旦题目变形就傻眼。这里我把状态设计、转移方程、循环顺序全部拆开讲。2.1 状态设计dp[k][i][j]到底代表什么floyd算法的本质是动态规划。既然是动态规划第一步就是定义状态。这里的关键在于一个视角转换允许经过的中间节点集合。我先把节点编号为0,1,2,...,n-1。定义状态dp[k][i][j] 从i到j只允许经过编号不超过k的节点作为中间节点时最短路径的长度。这里只允许经过编号不超过k的节点是什么意思比如dp[5][2][7]表示从2号节点到7号节点路径中间你只能经过编号小于等于5的节点0、1、2、3、4、5首尾2和7不算在中间节点限制里。这个限制不是说你一定要经过这些节点而是说你能用到的中转站只在这个集合里。很多教材会写dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])如果你觉得抽象可以把它想象成现在第k号节点要解锁了那么在计算从i到j的最短路时可以尝试把k加进允许中转的名单里。要么不加沿用旧路径要么加路径变成i先到k再k到j。注意当k从0逐步增大到n-1时允许的中转节点集合越来越大。等k到n-1时所有节点都被允许了dp[n-1][i][j]就是真正的全局最短路径。这就是为什么floyd算法只需要跑完一轮k从0到n-1的循环答案就出来了。2.2 状态转移方程是怎么来的现在把上一节的状态展开。假设我已经知道了dp[k-1]的所有值也就是说我已经算出了只允许经过编号0到k-1这些节点时任意两点间的最短路。现在要算dp[k][i][j]。从i到j只允许经过编号不超过k的节点有两种情况第一种最短路压根不经过节点k。那么路径上的节点全部落在0到k-1的集合里路径长度就是dp[k-1][i][j]。第二种最短路确实经过了节点k。那么这条路径就可以拆成两段从i到k的路径和从k到j的路径。由于k是允许范围内编号最大的节点而且路径上不会出现其他编号大于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] )这个递推式成立的前提是如果最短路经过k那么把它拆成两段后每一段的内部都不会再经过编号大于k的节点。这由k是当前允许集合中最大编号保证。现在发现一个关键点在计算dp[k]这一层时只用到了dp[k-1]层的数据。这是典型的滚动结构所以不需要真的开一个三维数组直接在二维数组上原地更新就行。为什么原地更新不会污染后面的计算因为dp[k][i][k]和dp[k][k][j]其实就是dp[k-1][i][k]和dp[k-1][k][j]——节点k自己作为端点中间节点集合里加不加k都不影响它本身的值。所以你可以放心用同一个二维数组覆盖更新。2.3 为什么k必须放在最外层重点这是一个必须刻进DNA里的点k循环必须放在最外层。我可以负责任地说我见过至少十个初学者把循环顺序写成i、j、k然后跑出完全错误的结果又死活找不到bug。原因要从状态转移的依赖关系说起。dp[k][i][j]依赖的是dp[k-1][i][j]、dp[k-1][i][k]和dp[k-1][k][j]。也就是说每一轮k的更新依赖的是上一轮k-1的结果。如果k循环不在最外层那么当你在计算dp[i][j]时可能dp[i][k]已经被更大的k更新过了也可能还没被更新过整个计算的语义就混乱了。用更直观的话说floyd算法是一个逐步开放中间节点的过程。第k轮时名单里只有0到k这些节点。如果你把k放到最内层就相当于在计算dp[i][j]时对于不同的i、j允许开放到的节点集合不一致这完全破坏了动态规划的状态定义。这里我加一个程序员视角的经验如果你在调试时发现结果比预期大偏大多半是循环顺序错了——最内层的k导致部分状态没有正确传播如果你发现结果偏小甚至出现比真值还小的路径大概率是图里有负权回路或者INF设置不合理导致无效值参与了松弛。2.4 负边权为什么可行、与贪心的本质区别很多人学到这里会疑惑Dijkstra明明对负边无能为力为什么floyd就行答案在于floyd是动态规划而不是贪心。Dijkstra的策略是每轮锁定一个当前最近的点这个策略依赖一个前提已经锁定的节点不可能再被其他节点更新。一旦出现负边这个前提就不成立贪心策略失效。动态规划则不搞锁定它遍历所有可能的中间节点组合把所有情况都纳入比较。状态转移方程本身不依赖任何当前最优的假设它只是老老实实地枚举经过k和不经过k两种可能。所以只要路径更新过程中能正常收敛即不存在负权回路导致路径无限变小floyd就能正确处理负边。这也解释了另一个常见疑问floyd为什么不能处理负权回路因为如果存在一个负权回路那么路径可以在回路里转无数圈距离越转越小最终会变成负无穷。这不是算法逻辑的缺陷而是问题本身无解。后面我会专门讲怎么用floyd的结果检测负权回路。3. 手写实现从邻接矩阵到完整可运行代码说完了理论进入实操环节。这里我给出一个完整的Python实现包括初始化、主循环、路径重建三个部分。为了贴合实际工程场景我还会解释一些容易被忽略的边界处理。3.1 初始化邻接矩阵、INF、自环、重边floyd算法的前提是有一张邻接矩阵。假设图有n个节点边可能以列表形式给出每条边是(u, v, w)表示从u到v有一条权重为w的有向边。如果是无向图记得要同时设置d[v][u] w。初始化有几个关键点第一d[i][i] 0。自己到自己距离是0这个必须设置否则算法会把自环当成无穷大路径更新时也会出问题。第二没有直接边的位置设置为一个足够大的数INF表示不可达。第三如果有重边保留权重最小的那条。这个在竞赛题里很常见有时候出题人故意给你多组相同起点终点的边你要取最小值。初始化代码def init_graph(n, edges, directedTrue): INF 10**15 d [[INF] * n for _ in range(n)] for i in range(n): d[i][i] 0 for u, v, w in edges: if w d[u][v]: d[u][v] w if not directed: d[v][u] w return d这里INF取10^15在Python里完全够用而且加法不会溢出。如果是C选手我后面会专门讲0x3f3f3f3f这个经典值的选择逻辑。3.2 floyd()主循环实现有了邻接矩阵主循环就是标准的三个嵌套fordef floyd(d): n len(d) for k in range(n): for i in range(n): if d[i][k] INF: continue dik d[i][k] for j in range(n): nd dik d[k][j] if nd d[i][j]: d[i][j] nd return d这里做了一个小优化如果d[i][k]已经是INF说明从i到不了k那松弛就没有意义直接跳过。另外把d[i][k]存到一个临时变量dik里避免在j循环里反复读取二维数组这在n较大时能省不少时间。实测下来这个简单的局部变量优化在Python里能带来10%~20%的性能提升。完成之后d[i][j]就是任意两点间的最短距离。3.3 路径重建nxt数组回溯很多场景下光知道最短距离还不够你还得把具体路径打印出来。比如地图导航里用户要的不是距离是10公里而是怎么走。这需要额外维护一个next数组。next[i][j]表示从i到j的最短路径上i的下一个节点是谁。初始化时如果存在边i-j则next[i][j] j。在松弛过程中如果发现通过k中转更好就把next[i][j]更新为next[i][k]因为此时从i出发的第一步和去k的第一步是相同的。def floyd_with_path(d): n len(d) nxt [[-1] * n for _ in range(n)] for i in range(n): for j in range(n): if d[i][j] ! INF: nxt[i][j] j for k in range(n): for i in range(n): if d[i][k] INF: continue for j in range(n): nd d[i][k] d[k][j] if nd d[i][j]: d[i][j] nd nxt[i][j] nxt[i][k] return d, nxt def get_path(nxt, s, t): if nxt[s][t] -1: return None path [s] while s ! t: s nxt[s][t] path.append(s) return path这个写法非常实用。注意如果s和t之间不可达nxt[s][t]会一直是-1返回None调用方要做好判空。路径重建的时间复杂度是O(L)L是路径长度几乎可以忽略不计。3.4 复杂度分析与空间优化时间复杂度是O(V³)这个没法优化除非换算法。空间复杂度是O(V²)因为需要维护一个二维距离矩阵和一个可选的二维next矩阵。在V500时两个矩阵各25万个元素现代计算机毫无压力但V2000时光一个距离矩阵就是400万个元素再加next矩阵就逼近64MB了需要注意内存。有一种削减空间的办法不需要路径重建时千万别开next数组省一半内存。如果需要路径重建但内存紧张可以考虑用short、int32等紧凑类型存储next值。另外如果只关心是否存在路径而不管长度可以把距离矩阵改成布尔矩阵转移方程变成或运算。这就是著名的传递闭包算法Warshall算法下一节单独讲。3.5 传递闭包改一行代码的妙用Warshall算法是floyd算法的一个变种用来求有向图的传递闭包判断任意两点之间是否存在路径而不关心距离。实现时把距离比较换成逻辑运算即可def transitive_closure(adj): n len(adj) reach [row[:] for row in adj] for k in range(n): for i in range(n): if reach[i][k]: for j in range(n): reach[i][j] reach[i][j] or reach[k][j] return reach这里的reach[i][j]为True表示从i可以到达j。初始时reach[i][i] True、存在直接边则为True。这个算法时间复杂度同样是O(V³)但常数非常小在判断图的弱连通性、检测是否有环等场景里使用率很高。我在实际做知识图谱相关的项目时就多次用传递闭包判断两个实体之间是否存在间接关联实现起来比BFS逐点搜索要省心得多——一次成型查任意两点都是O(1)。4. 关键参数与边界INF怎么取、负环怎么判算法本身不难难的是把边界条件处理干净。这一节我专门讲三个实操中逃不掉的问题不可达值INF怎么取、怎么检测负权回路、以及怎么利用floyd求最小环。4.1 INF选择的数学依据INF的选择看似简单其实暗藏杀机。它必须满足一个条件INF 任意有限值仍然是一个足够大的数不能出现溢出变成负数或小数的悲剧。C里经典做法是取0x3f3f3f3f也就是十进制1061109567。为什么是这个数因为0x3f3f3f3f 0x3f3f3f3f 2122219134仍然小于int的最大值2147483647。你用memset(arr, 0x3f, sizeof(arr))可以快速把整个数组初始化为0x3f3f3f3f这是竞赛圈常用的技巧。但如果你用0x7fffffffint最大值作为INF那一旦做INF INF就会整数溢出变成负数松弛条件nd d[i][j]就会把大量不可达误判成可达结果全乱套。这是很多C新手栽过的坑。Python里没有int溢出问题但也不建议用float(inf)因为浮点数和整数混用可能引入精度问题。比如float(inf) 1仍然等于inf没问题但某些数值较大时浮点表示会丢精度。稳妥的做法是设一个足够大的整数比如1015或1018确保它大于所有可能的最短路径长度之和。路径最大长度一般是边数 × 最大边权绝大多数题目里10**15绰绰有余。4.2 负权回路检测的原理与时机如果图里存在负权回路从某个点出发绕一圈还能让距离变小那么最短路径就变成了负无穷floyd的结果会逐渐变成非常小的负数。算法结束时怎么发现这个问题非常简单跑完floyd之后检查对角线。如果存在某个i使得d[i][i] 0那说明存在负权回路。原理是初始时d[i][i] 0。如果存在负权回路那么从i出发走一圈回到i路径长度是负数floyd会在松弛过程中把这个负值更新到d[i][i]上。所以只要d[i][i]变负就说明图中存在负权回路。实际编码时我一般会在floyd结束后加一个检查def has_negative_cycle(d): n len(d) for i in range(n): if d[i][i] 0: return True return False注意这个检查必须在算法完整跑完之后再做不能在中途判断因为d[i][i]可能在后续轮次被继续更新。4.3 拓展应用利用floyd()求最小环既然谈到环路顺便分享一个floyd的经典扩展求无向图或有向图中的最小环长度。这个技巧在不少竞赛题里会出现而且它用到了floyd过程中k作为最大编号节点的特性。思路是在第k轮更新前dp矩阵里存储的是只允许经过0到k-1号节点的最短路径。此时对于任意一对i、j如果存在一条边i-k和一条边k-j再加上dp[i][j]中间不经过k就能构成一个包含k的环环长为dp[i][j] g[i][k] g[k][j]。所以要在用k更新距离矩阵之前先计算最小环否则k被当作中转点后会破坏不经过k的前提。核心代码模板def min_cycle(n, d, g): INF 10**15 ans INF for k in range(n): for i in range(k): for j in range(i 1, k): if d[i][j] ! INF and g[i][k] ! INF and g[k][j] ! INF: ans min(ans, d[i][j] g[i][k] g[k][j]) # 然后再用k更新d for i in range(n): for j in range(n): if d[i][k] d[k][j] d[i][j]: d[i][j] d[i][k] d[k][j] return ans这个先查环、再更新的顺序踩坑率极高很多人直接在最前面跑一遍ans min(ans, d[i][j] d[i][k] d[k][j])就会把k自己中转的路径也算进去导致重复计算或错误地出现长度为2的假环。我自己第一次写这个扩展时也踩了坑后来看到环必须经过编号最大的节点k这个视角才彻底明白。5. 常见问题与排查技巧实录这一节是我压箱底的经验。我把自己在学习和实践中遇到过的、以及在帮别人debug时看到过的典型问题整理成一个速查表顺便给出调试思路。5.1 常见错误速查表症状可能原因解决办法结果比正确答案大k循环不在最外层初始化INF太大导致加法溢出把k放到最外层在松弛前判断INF结果比正确答案小INF设置太小不可达路径参与了松弛存在负权回路增大INF检查对角线是否有负数带负数边时结果不对图里有负权回路没被检测出来循环结束后检查d[i][i] 0路径重建时死循环nxt数组初始化错误更新nxt逻辑写错检查nxt[i][j]是否在松弛成功时才更新无向图结果不对称加边时只写了一个方向确保双向都写且重边取最小节点编号从1开始导致越界忘记把输入编号减1统一在读取时转换下标这些坑我都一个个踩过。尤其是结果比答案小这种情况排查起来最耗时因为你会怀疑是自己的逻辑错了而实际上往往是INF取值太小负的不可达值在参与比较。5.2 调试floyd的三板斧如果代码逻辑复杂到你不确定哪里出错我建议按下面三步排查第一造一个极小规模用例比如4个节点的有向图手动演算一遍和程序输出逐项核对。4个节点时只有64种i、j、k组合手算完全可行。我通常会在纸上画一个4阶矩阵按k0,1,2,3四轮手工更新这样能精准定位是哪一轮开始出错的。第二加日志输出中间状态。在每一轮k结束后打印整个距离矩阵。如果某一轮更新后出现了非预期的值就定位到那一轮的某次松弛。这个方法虽然笨但非常有效。很多写算法的人忽略了中间状态可视化的威力实际上它比单步断点调试更直观。第三对照朴素实现验证。写一个基于DFS或BFS的暴力最短路搜索仅限小图和floyd的结果对比。如果floyd和暴力结果不一致那就是floyd实现的问题如果一致那可能是你的暴力搜索本身有bug。这种双实现互验是算法题最稳妥的兜底方案。5.3 刷题与工程中的选型建议最后给点选型层面的建议这可能帮你省下大把时间。数据范围在V ≤ 500时优先考虑floyd。不管是竞赛还是面试看到这个规模基本可以放心写三重循环时间充裕且代码简洁。V在1000~2000之间时floyd的三重循环在Python里会非常吃力10亿次操作即使优化到极致也可能要几十秒。这时候应该改用Dijkstra跑n遍或者用Johnson算法先Bellman-Ford重赋权再跑n遍Dijkstra。但在稀疏图里n遍Dijkstra优势明显。V超过2000时除非题目极其特殊否则几乎必须换思路。比如利用图的稀疏性做单源算法或者用最小生成树等特殊结构。别死磕floyd。工程上还有一个考虑如果图是动态变化的频繁加边、删边floyd每次都要全量重跑效率太低。这时候可以考虑用增量式算法或者干脆改用单源查询缓存。floyd更适合图基本不变、查询非常频繁的场景因为查询一次只要O(1)预先计算一次的成本可以被大量查询摊薄。说回我自己的体会。floyd()算法是我用过的所有图中最短路算法里最小而美的一个。它的代码量少到极致背后的动态规划思想却非常深刻——通过逐步放开中间节点集合完成全局最优解的计算。很多人在初学时会觉得它不过是一个三重循环但当你真正理解了为什么k在最外层、为什么可以原地更新、为什么负权边可行之后你会发现这对动态规划状态设计的理解会提升一个层次。最后分享一个小技巧我在本地会保存一个floyd算法的最小模板包含距离计算和路径重建做题时直接复制粘贴只改初始化部分。使用频率高、代码稳定的算法值得这样沉淀一套模板能省下大量重复敲代码的时间。希望这篇文章能帮你彻底搞懂floyd()算法并在实际项目或刷题中少踩几个坑。