1. 从“交通协管员”说起Floyd到底在算什么看到标题里那句“热心肠的交通协管员”我忍不住乐了——这比喻确实戳中了 Floyd 算法的精髓。你要是被临时抓来做一个全源最短路径的需求手边又没有现成的图算法库Floyd 算法往往是第一个能跑通的选择代码骨架短到离谱核心就是三层 for 循环嵌套一个 if十几行搞定而且它能一次性算出所有点对之间的最短距离。把算法想象成一个场景就很好记城市里每个路口都有一位拿着地图的协管员编号 k 的协管员负责排查所有可能经过自己路口的路线。他拦住每一个路过的人问“你从 i 到 j绕道我这儿 k 走一圈是不是比你现在地图上标的路线更近”只要答案是“是”他就当场把地图上 i 到 j 的距离改掉。等编号 0、1、2……一直到 n-1 的协管员都挨个问完一遍全城任意两点之间的最短距离就齐了。这句话基本就是 Floyd 算法的全部内容了。它的正式名字叫 Floyd-Warshall 算法解决的是全源最短路径问题all-pairs shortest paths也就是一次性求出图中任意两个节点之间的最短距离。它不要求图是连通的也不要求边权都是正数只要没有负环就能正常工作。写网络拓扑的最短路由、做城市交通的简化模型、给游戏地图做寻路预处理或者刷算法题遇到“任意两两距离”的需求它都是最省脑子的选择。1.1 “全源”到底是个什么需求很多刚接触图论的人会混淆“全源”和“单源”。单源最短路径只关心一个固定起点到所有其他点的距离典型代表是 Dijkstra 和 Bellman-Ford而全源关心的是所有点对之间的距离Floyd 就是干这个的。举个实际场景假设你维护一张城市交通图节点是地铁站边是站与站之间的通行时间。产品经理说“我要做一个查询用户随便选两个站立刻显示预计通勤时间”。如果每次查询都跑一次 Dijkstra用户多、查询一多就扛不住更合理的方式是启动时用 Floyd 把所有站点两两之间的时间都算好查询直接查表O(1) 返回。Floyd 这个“预处理查表”的定位什么时候都不会过时。1.2 它和 Dijkstra 的关系一句话讲清Dijkstra 是“一个起点、逐个扩散”像个只服务一个客户的快递员Floyd 是“所有人都问一遍所有人”像个把整座城市的地图全部重画一遍的制图员。两者的核心思想完全不同Dijkstra 基于贪心每轮挑当前最近的未确定节点要求边权非负。Floyd 基于动态规划把所有中间节点依次“放行”天然支持负权边。Bellman-Ford 也是动态规划思路但它只服务单源Floyd 是它“全源版”的亲戚。所以在选型时只要需求是“所有点对最短路径”优先想 Floyd如果只是单源且图很大、边权非负那 Dijkstra 从任何角度都比硬跑 Floyd 划算。这个选型权衡我在第 4 节专门展开。2. 代码骨架三层循环和那个不能乱的 k直接上骨架。这里以 Python 为例图的节点编号从 0 到 n-1dist 是一个 n×n 的二维矩阵dist[i][j] 表示当前已知的 i 到 j 的最短距离INF 10 ** 18 def floyd_warshall(n, dist): # dist 是 n x n 矩阵初始化时 # dist[i][i] 0dist[i][j] 边权有边否则为 INF for k in range(n): # 中转点编号 0 到 k 的路口依次放行 for i in range(n): # 起点 if dist[i][k] INF: continue # i 到 k 不可达跳过整行省时间 base dist[i][k] row_i dist[i] row_k dist[k] for j in range(n): # 终点 nd base row_k[j] if nd row_i[j]: row_i[j] nd return dist如果看最朴素的写法那真的是网上一搜一大把的“三行核心”for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j]两种写法功能完全等价区别只是后者没做不可达时的跳过优化。对 Python 来说这个continue能省下大量无效加法时间对 C 来说写不写都行编译器优化得好但写上也没坏处。C 版本大概长这样const long long INF 1e18; // dist 初始化dist[i][i] 0, dist[i][j] 边权, 其余为 INF for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; long long t dist[i][k]; for (int j 0; j n; j) { if (t dist[k][j] dist[i][j]) dist[i][j] t dist[k][j]; } } }2.1 初始化矩阵别小看 INF 和 0 的安排骨架再漂亮初始化做错一样全盘皆输。Floyd 的矩阵初始化就三条规则dist[i][i] 0自己到自己的距离必然是 0。如果 i 到 j 有一条权值为 w 的边则dist[i][j] w。如果不直接相连dist[i][j] INF表示“当前还不知道怎么走”。这里面最容易犯的错有两类。第一类是忘了把对角线初始化成 0结果算法跑完每个节点到自己的最短距离反而变成绕一圈回来的正数全盘错误。第二类是重边处理输入里 i 到 j 可能给了多条边你要在初始化阶段就取最小值而不是后来的赋值把更优的边覆盖掉。常规写法是每次读边都做一次dist[u][v] min(dist[u][v], w)不要直接赋值。2.2 为什么 k 必须放在最外层这是 Floyd 最容易被人忽略、也最值得讲透的点。为什么中间节点 k 的循环必须是最外层换过来行不行用动态规划的语言说定义D[k][i][j]为“只允许把编号 0 到 k 这些节点当作中间人时i 到 j 的最短距离”。那么D[k][i][j]只有两种可能不经过新放行的节点 k那就是D[k-1][i][j]经过 k那就是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])这个递推式的含义非常像“逐轮放行路口”第 0 轮只允许经过路口 0第 1 轮允许经过路口 0 和 1以此类推。因为第 k 轮的值只依赖第 k-1 轮所以 k 必须当作外层循环一层一层往外扩。如果 k 放在内层就等于每一轮都没有“完整放行一个节点”的过程依赖关系全乱算出来的很可能是错误答案——某些需要连续经过多个中转点的路径在单次遍历中根本组合不出来。还有个小问题为什么可以原地更新dist[i][j]不用开一个三维数组存所有D[k]因为第 k 轮里dist[i][k]和dist[k][j]即使被更新也是“经过 k 自己”形成的路径比如 i → … → k → … → k。只要没有负环最短路径一定可以取成不重复经过任何节点的简单路径把绕回 k 的那一段删掉只会更短。所以第 k 轮里dist[i][k]、dist[k][j]的值和上一轮相比不会变得更优原地震荡是安全的。2.3 用一个 4 节点小图把骨架跑一遍光说不练假把式我用一个真实小图手算一遍。假设有 4 个节点边如下0 → 1 权 30 → 3 权 71 → 2 权 21 → 3 权 42 → 3 权 1初始矩阵∞ 表示不可达i\j0123003∞7130242∞20137410第 0 轮k0只放行节点 0检查以后发现没有任何一条路径因为经过节点 0 变得更短矩阵不变。这很正常因为节点 0 的入度有限。第 1 轮k1放行节点 1重点来了。0 到 2 原来不可达但 0 → 1 → 2 的代价是 3 2 5于是dist[0][2]从 ∞ 变成 5对称地2 到 0 也变成 5。i\j012300357130242520137410第 2 轮k2放行节点 20 到 3 原来走直连是 7现在 0 → 2 → 3 是 5 1 6更短更新同理 3 到 0 也变成 6。1 到 3 原来是直连 4现在 1 → 2 → 3 是 2 1 3也更新。第 3 轮k3放行节点 3检查所有 i、j 后发现没有再能压缩的距离。最终矩阵i\j012300356130232520136310注意 0 到 3 的最短距离不是直连的 7而是绕行得到的 6这个“绕行”正是 Floyd 逐轮放行中转节点后自动发现的。很多初学者跑完代码发现答案和自己肉眼看出的一致就松了口气但对这种“非直观路径”的推导过程多复盘几遍才能真理解 k 的作用。3. 从“能跑”到“能用”路径还原、负环检测、防溢出考试和面试里Floyd 通常只要求你能输出最短距离矩阵但到了真实项目里用户要的是“路怎么走”不是一串数字。所以路径还原、负环检测、INF 防溢出这三件事才是把骨架从“能跑”变成“能用”的关键。3.1 路径还原距离有了路怎么打印想打印具体路径最简单可靠的办法是维护一个nxt矩阵nxt[i][j]记录从 i 到 j 的最短路径上i 出发后下一步应该走到哪个节点。def floyd_with_path(n, dist): nxt [[-1] * n for _ in range(n)] for i in range(n): for j in range(n): if i ! j and dist[i][j] INF: nxt[i][j] j # 默认直连下一步就是 j for k in range(n): for i in range(n): if dist[i][k] INF: continue for j in range(n): nd dist[i][k] dist[k][j] if nd dist[i][j]: dist[i][j] nd nxt[i][j] nxt[i][k] # i 先沿 i 到 k 的最短路径走 return dist, nxt def print_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为什么更新时写nxt[i][j] nxt[i][k]因为新的最短路径 i → j 是“先走 i 到 k 的最短路再接 k 到 j”所以从 i 出发的第一步和 i 到 k 的最短路第一步完全相同也就是nxt[i][k]。这个赋值逻辑在更新距离时同步做等算法结束整条路径就串联起来了。我用这个方案在多个项目里打印过路线从来没出过问题。3.2 负环检测dist[i][i] 变成负数就是警报Floyd 一个被低估的能力是检测负环。如果图中存在一个环环上所有边权之和为负那么最短路径就没有定义——你可以绕着负环无限转圈距离越来越小。Floyd 跑完之后负环的判别条件极其简单if any(dist[i][i] 0 for i in range(n)): print(图中存在负环)原理很直接如果存在负环那么环上的任意一个节点 v 沿着环走一圈回到自己总代价是负的dist[v][v]就会被更新成负数。初始化时对角线全是 0跑完后任何对角线元素小于 0都说明存在负环。注意这不代表 Floyd“算出了”最短路径——负环存在时最短路径本身无意义算法给出的只是它能给出的结果你要做的是检测到后去处理业务逻辑而不是拿着错误的距离继续算。3.3 INF 的坑不同语言不同选法这是新手最容易踩、而且踩了还不自知的一个坑。Floyd 的核心操作是dist[i][k] dist[k][j]如果dist[i][k]是 INF那这个加法本身就可能出问题。C 里常见做法是用0x3f3f3f3f约 10 亿作为 int 的 INF因为两个0x3f3f3f3f相加约 21.2 亿还不会超过 int 上限 21.47 亿。但这是把玩具撑到了极限边缘一旦边权稍大就容易溢出成负数负的“无穷大”会让算法彻底崩溃。我的习惯是 C 一律用long long配合1e18完全避开溢出的可能性。Python 不存在整数溢出但建议用10 ** 18这种“一眼就知道不会真的被加到”的大数别用float(inf)——浮点无穷和整数混合运算容易带来脏数据而且打印结果时很难看。还有一个容易忽略的初始化细节读边的时候如果两点之间有多条边要把dist[i][j]设成所有边权的最小值。图论题里“重边取最小”是基本规矩但实际代码里很多人直接覆盖赋值导致后面全错排查半天才发现是初始化的问题。4. 复杂度与选型什么时候该用它什么时候赶紧换Floyd 不是银弹。它最大的软肋是时间复杂度 O(n³)空间复杂度 O(n²)。面试题默认 n 在几百以内随便跑但真实工程中 n 上到几千甚至上万时你必须有清醒的选型判断。4.1 O(n³) 到底是多大n 的规模直接决定一切。内层轮数就是 n³ 次n内层迭代总数C 实测体感Python 体感100100 万毫秒级0.1 秒级3002700 万0.2 秒左右2 秒左右5001.25 亿0.5 秒左右5 到 8 秒100010 亿3 到 5 秒30 秒以上基本别想以上是粗略量级跟机器、图密度、是否做了 INF 跳过都有关系但方向是确定的n 超过 1000Python 就该慎重n 超过 2000C 也要掂量掂量。空间上n×n 的 long long 矩阵n5000 时就是 5000² × 8 字节 ≈ 200MB已经逼近很多服务的内存红线。4.2 和“跑 n 次 Dijkstra”的对比全源最短路径不止 Floyd 一条路。常见对比方案时间复杂度优势短板FloydO(n³)实现极简支持负权边只适合小 n 或稠密图跑 n 次 DijkstraO(n·(m n log n))稀疏图大杀器不支持负权边代码复杂跑 n 次 Bellman-FordO(n²·m)支持负权边一般不如 Johnson 实用JohnsonO(n·m n² log n)稀疏负权边的最优选实现复杂度最高选型逻辑其实很朴素如果图是稠密图m 接近 n²Floyd 和 Dijkstra 跑 n 次在复杂度上差不多但 Floyd 代码短一个量级肯定选 Floyd如果图是稀疏图m 接近 n且 n 很大跑 n 次 Dijkstra 通常完胜因为 O(n·m) 远小于 O(n³)。Johnson 算法适合“n 大、有负权边、偏稀疏”的折中场景但除非必要我很少在项目里主动用因为实现成本高出 bug 概率大。4.3 顺带一提Warshall 传递闭包和它是一家人Floyd 有个非常著名的近亲——Warshall 算法用于计算传递闭包transitive closure也就是回答“i 能不能通过若干条边到达 j”。它和 Floyd 共享同一个骨架只是把“距离远近”换成了“是否可达”def transitive_closure(n, reach): # reach[i][j] 是布尔值表示 i 能否到达 j 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]这段代码我经常在数据库权限关系推导、依赖关系分析里用到。Floyd 处理“最短路”Warshall 处理“可达性”两个名字绑在一起本质都是同一个“逐轮放行中间节点”的动态规划思路。你理解了 Floyd 的 k 循环Warshall 就是顺手的事。5. 实测中的坑与提速心得骨架写熟之后真正让你头秃的往往是那些不起眼的小问题。我把自己这些年踩过的坑和总结出来的提速招数集中列一下基本覆盖了 Floyd 在实际使用中的高频雷区。5.1 初始化阶段就会犯的三个错第一重边覆盖。前面说过多条同向边必须取最小权不是后读的覆盖先读的。第二点编号从 1 开始。很多算法题习惯把节点编号成 1 到 n你直接套 0 基数组就容易越界或漏点正确做法是数组开到 (n1)×(n1)循环从 1 到 n。第三对角线初始化。dist[i][i]必须为 0但也要注意输入里如果有负的自环i 到 i 的负权边那就直接说明存在负环了算法跑完对角线自然是负数。这三个错我几乎在每次带新人做图论题时都能见到每一条都可能导致 Debug 两小时发现是初始化写错。5.2 Python 版提速招数Python 跑 Floyd 天生吃亏但有几个立竿见影的优化手段跳过不可达行if dist[i][k] INF: continue如果 i 到 k 不可达整行都不用算。局部变量绑定把dist[i]和dist[k]提出来赋值给本地变量row_i、row_k减少二维数组寻址开销。避免在循环里重复计算dist[i][k]先算好base dist[i][k]。对称图只用算一半如果确认图是无向图可以只更新 j ≥ i 的下三角或上三角再对称复制。但这会干扰路径还原的nxt矩阵维护非必要不推荐先保证正确再谈优化。这些优化合起来n500 的 Python 版可以从 8 秒压到 5 秒左右。想再快老实换 C 或 PyPy。5.3 几个实用变种瓶颈路径、必经点、特殊图Floyd 的骨架弹性比看起来大得多改一下松弛条件就能适配不同需求瓶颈路径最大容量路径把min和换成max和min即dist[i][j] max(dist[i][j], min(dist[i][k], dist[k][j]))可以求出“两点之间能使路径上最小边权最大化”的走法。这在水管流量、带宽规划、承重路线场景里很常见。必经点组合先跑一次 Floyd 得到全源距离然后对“必须经过节点集 X”的需求用dist[s][x] dist[x][t]组合查询。这种“预处理 查表”的思路比每次现场跑图快几个数量级。最小换乘次数边权全为 1 的无向图Floyd 跑完直接就是最少换乘数如果节点很多其实 BFS 从每个点跑一遍更快但 Floyd 的代码确实短。我个人在实际项目里的一个体会是Floyd 的价值不在于它快而在于它稳。当你的图规模不大、又需要“任意点对之间某种最优度量”时它的代码量是所有方案里最小的正因为短出 bug 的面也小后期维护的人看一眼就懂。有一回我给一个调度系统做城市间运费预计算数据量只有几十个节点我连 Dijkstra 都没想直接上 Floyd半小时内上线。当然等节点规模真的大了我会毫不犹豫换 Dijkstra 或 Johnson但那是另一个故事了。 Floyd算法详解：从三层循环到全源最短路径的工程实践
1. 从“交通协管员”说起Floyd到底在算什么看到标题里那句“热心肠的交通协管员”我忍不住乐了——这比喻确实戳中了 Floyd 算法的精髓。你要是被临时抓来做一个全源最短路径的需求手边又没有现成的图算法库Floyd 算法往往是第一个能跑通的选择代码骨架短到离谱核心就是三层 for 循环嵌套一个 if十几行搞定而且它能一次性算出所有点对之间的最短距离。把算法想象成一个场景就很好记城市里每个路口都有一位拿着地图的协管员编号 k 的协管员负责排查所有可能经过自己路口的路线。他拦住每一个路过的人问“你从 i 到 j绕道我这儿 k 走一圈是不是比你现在地图上标的路线更近”只要答案是“是”他就当场把地图上 i 到 j 的距离改掉。等编号 0、1、2……一直到 n-1 的协管员都挨个问完一遍全城任意两点之间的最短距离就齐了。这句话基本就是 Floyd 算法的全部内容了。它的正式名字叫 Floyd-Warshall 算法解决的是全源最短路径问题all-pairs shortest paths也就是一次性求出图中任意两个节点之间的最短距离。它不要求图是连通的也不要求边权都是正数只要没有负环就能正常工作。写网络拓扑的最短路由、做城市交通的简化模型、给游戏地图做寻路预处理或者刷算法题遇到“任意两两距离”的需求它都是最省脑子的选择。1.1 “全源”到底是个什么需求很多刚接触图论的人会混淆“全源”和“单源”。单源最短路径只关心一个固定起点到所有其他点的距离典型代表是 Dijkstra 和 Bellman-Ford而全源关心的是所有点对之间的距离Floyd 就是干这个的。举个实际场景假设你维护一张城市交通图节点是地铁站边是站与站之间的通行时间。产品经理说“我要做一个查询用户随便选两个站立刻显示预计通勤时间”。如果每次查询都跑一次 Dijkstra用户多、查询一多就扛不住更合理的方式是启动时用 Floyd 把所有站点两两之间的时间都算好查询直接查表O(1) 返回。Floyd 这个“预处理查表”的定位什么时候都不会过时。1.2 它和 Dijkstra 的关系一句话讲清Dijkstra 是“一个起点、逐个扩散”像个只服务一个客户的快递员Floyd 是“所有人都问一遍所有人”像个把整座城市的地图全部重画一遍的制图员。两者的核心思想完全不同Dijkstra 基于贪心每轮挑当前最近的未确定节点要求边权非负。Floyd 基于动态规划把所有中间节点依次“放行”天然支持负权边。Bellman-Ford 也是动态规划思路但它只服务单源Floyd 是它“全源版”的亲戚。所以在选型时只要需求是“所有点对最短路径”优先想 Floyd如果只是单源且图很大、边权非负那 Dijkstra 从任何角度都比硬跑 Floyd 划算。这个选型权衡我在第 4 节专门展开。2. 代码骨架三层循环和那个不能乱的 k直接上骨架。这里以 Python 为例图的节点编号从 0 到 n-1dist 是一个 n×n 的二维矩阵dist[i][j] 表示当前已知的 i 到 j 的最短距离INF 10 ** 18 def floyd_warshall(n, dist): # dist 是 n x n 矩阵初始化时 # dist[i][i] 0dist[i][j] 边权有边否则为 INF for k in range(n): # 中转点编号 0 到 k 的路口依次放行 for i in range(n): # 起点 if dist[i][k] INF: continue # i 到 k 不可达跳过整行省时间 base dist[i][k] row_i dist[i] row_k dist[k] for j in range(n): # 终点 nd base row_k[j] if nd row_i[j]: row_i[j] nd return dist如果看最朴素的写法那真的是网上一搜一大把的“三行核心”for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j]两种写法功能完全等价区别只是后者没做不可达时的跳过优化。对 Python 来说这个continue能省下大量无效加法时间对 C 来说写不写都行编译器优化得好但写上也没坏处。C 版本大概长这样const long long INF 1e18; // dist 初始化dist[i][i] 0, dist[i][j] 边权, 其余为 INF for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; long long t dist[i][k]; for (int j 0; j n; j) { if (t dist[k][j] dist[i][j]) dist[i][j] t dist[k][j]; } } }2.1 初始化矩阵别小看 INF 和 0 的安排骨架再漂亮初始化做错一样全盘皆输。Floyd 的矩阵初始化就三条规则dist[i][i] 0自己到自己的距离必然是 0。如果 i 到 j 有一条权值为 w 的边则dist[i][j] w。如果不直接相连dist[i][j] INF表示“当前还不知道怎么走”。这里面最容易犯的错有两类。第一类是忘了把对角线初始化成 0结果算法跑完每个节点到自己的最短距离反而变成绕一圈回来的正数全盘错误。第二类是重边处理输入里 i 到 j 可能给了多条边你要在初始化阶段就取最小值而不是后来的赋值把更优的边覆盖掉。常规写法是每次读边都做一次dist[u][v] min(dist[u][v], w)不要直接赋值。2.2 为什么 k 必须放在最外层这是 Floyd 最容易被人忽略、也最值得讲透的点。为什么中间节点 k 的循环必须是最外层换过来行不行用动态规划的语言说定义D[k][i][j]为“只允许把编号 0 到 k 这些节点当作中间人时i 到 j 的最短距离”。那么D[k][i][j]只有两种可能不经过新放行的节点 k那就是D[k-1][i][j]经过 k那就是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])这个递推式的含义非常像“逐轮放行路口”第 0 轮只允许经过路口 0第 1 轮允许经过路口 0 和 1以此类推。因为第 k 轮的值只依赖第 k-1 轮所以 k 必须当作外层循环一层一层往外扩。如果 k 放在内层就等于每一轮都没有“完整放行一个节点”的过程依赖关系全乱算出来的很可能是错误答案——某些需要连续经过多个中转点的路径在单次遍历中根本组合不出来。还有个小问题为什么可以原地更新dist[i][j]不用开一个三维数组存所有D[k]因为第 k 轮里dist[i][k]和dist[k][j]即使被更新也是“经过 k 自己”形成的路径比如 i → … → k → … → k。只要没有负环最短路径一定可以取成不重复经过任何节点的简单路径把绕回 k 的那一段删掉只会更短。所以第 k 轮里dist[i][k]、dist[k][j]的值和上一轮相比不会变得更优原地震荡是安全的。2.3 用一个 4 节点小图把骨架跑一遍光说不练假把式我用一个真实小图手算一遍。假设有 4 个节点边如下0 → 1 权 30 → 3 权 71 → 2 权 21 → 3 权 42 → 3 权 1初始矩阵∞ 表示不可达i\j0123003∞7130242∞20137410第 0 轮k0只放行节点 0检查以后发现没有任何一条路径因为经过节点 0 变得更短矩阵不变。这很正常因为节点 0 的入度有限。第 1 轮k1放行节点 1重点来了。0 到 2 原来不可达但 0 → 1 → 2 的代价是 3 2 5于是dist[0][2]从 ∞ 变成 5对称地2 到 0 也变成 5。i\j012300357130242520137410第 2 轮k2放行节点 20 到 3 原来走直连是 7现在 0 → 2 → 3 是 5 1 6更短更新同理 3 到 0 也变成 6。1 到 3 原来是直连 4现在 1 → 2 → 3 是 2 1 3也更新。第 3 轮k3放行节点 3检查所有 i、j 后发现没有再能压缩的距离。最终矩阵i\j012300356130232520136310注意 0 到 3 的最短距离不是直连的 7而是绕行得到的 6这个“绕行”正是 Floyd 逐轮放行中转节点后自动发现的。很多初学者跑完代码发现答案和自己肉眼看出的一致就松了口气但对这种“非直观路径”的推导过程多复盘几遍才能真理解 k 的作用。3. 从“能跑”到“能用”路径还原、负环检测、防溢出考试和面试里Floyd 通常只要求你能输出最短距离矩阵但到了真实项目里用户要的是“路怎么走”不是一串数字。所以路径还原、负环检测、INF 防溢出这三件事才是把骨架从“能跑”变成“能用”的关键。3.1 路径还原距离有了路怎么打印想打印具体路径最简单可靠的办法是维护一个nxt矩阵nxt[i][j]记录从 i 到 j 的最短路径上i 出发后下一步应该走到哪个节点。def floyd_with_path(n, dist): nxt [[-1] * n for _ in range(n)] for i in range(n): for j in range(n): if i ! j and dist[i][j] INF: nxt[i][j] j # 默认直连下一步就是 j for k in range(n): for i in range(n): if dist[i][k] INF: continue for j in range(n): nd dist[i][k] dist[k][j] if nd dist[i][j]: dist[i][j] nd nxt[i][j] nxt[i][k] # i 先沿 i 到 k 的最短路径走 return dist, nxt def print_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为什么更新时写nxt[i][j] nxt[i][k]因为新的最短路径 i → j 是“先走 i 到 k 的最短路再接 k 到 j”所以从 i 出发的第一步和 i 到 k 的最短路第一步完全相同也就是nxt[i][k]。这个赋值逻辑在更新距离时同步做等算法结束整条路径就串联起来了。我用这个方案在多个项目里打印过路线从来没出过问题。3.2 负环检测dist[i][i] 变成负数就是警报Floyd 一个被低估的能力是检测负环。如果图中存在一个环环上所有边权之和为负那么最短路径就没有定义——你可以绕着负环无限转圈距离越来越小。Floyd 跑完之后负环的判别条件极其简单if any(dist[i][i] 0 for i in range(n)): print(图中存在负环)原理很直接如果存在负环那么环上的任意一个节点 v 沿着环走一圈回到自己总代价是负的dist[v][v]就会被更新成负数。初始化时对角线全是 0跑完后任何对角线元素小于 0都说明存在负环。注意这不代表 Floyd“算出了”最短路径——负环存在时最短路径本身无意义算法给出的只是它能给出的结果你要做的是检测到后去处理业务逻辑而不是拿着错误的距离继续算。3.3 INF 的坑不同语言不同选法这是新手最容易踩、而且踩了还不自知的一个坑。Floyd 的核心操作是dist[i][k] dist[k][j]如果dist[i][k]是 INF那这个加法本身就可能出问题。C 里常见做法是用0x3f3f3f3f约 10 亿作为 int 的 INF因为两个0x3f3f3f3f相加约 21.2 亿还不会超过 int 上限 21.47 亿。但这是把玩具撑到了极限边缘一旦边权稍大就容易溢出成负数负的“无穷大”会让算法彻底崩溃。我的习惯是 C 一律用long long配合1e18完全避开溢出的可能性。Python 不存在整数溢出但建议用10 ** 18这种“一眼就知道不会真的被加到”的大数别用float(inf)——浮点无穷和整数混合运算容易带来脏数据而且打印结果时很难看。还有一个容易忽略的初始化细节读边的时候如果两点之间有多条边要把dist[i][j]设成所有边权的最小值。图论题里“重边取最小”是基本规矩但实际代码里很多人直接覆盖赋值导致后面全错排查半天才发现是初始化的问题。4. 复杂度与选型什么时候该用它什么时候赶紧换Floyd 不是银弹。它最大的软肋是时间复杂度 O(n³)空间复杂度 O(n²)。面试题默认 n 在几百以内随便跑但真实工程中 n 上到几千甚至上万时你必须有清醒的选型判断。4.1 O(n³) 到底是多大n 的规模直接决定一切。内层轮数就是 n³ 次n内层迭代总数C 实测体感Python 体感100100 万毫秒级0.1 秒级3002700 万0.2 秒左右2 秒左右5001.25 亿0.5 秒左右5 到 8 秒100010 亿3 到 5 秒30 秒以上基本别想以上是粗略量级跟机器、图密度、是否做了 INF 跳过都有关系但方向是确定的n 超过 1000Python 就该慎重n 超过 2000C 也要掂量掂量。空间上n×n 的 long long 矩阵n5000 时就是 5000² × 8 字节 ≈ 200MB已经逼近很多服务的内存红线。4.2 和“跑 n 次 Dijkstra”的对比全源最短路径不止 Floyd 一条路。常见对比方案时间复杂度优势短板FloydO(n³)实现极简支持负权边只适合小 n 或稠密图跑 n 次 DijkstraO(n·(m n log n))稀疏图大杀器不支持负权边代码复杂跑 n 次 Bellman-FordO(n²·m)支持负权边一般不如 Johnson 实用JohnsonO(n·m n² log n)稀疏负权边的最优选实现复杂度最高选型逻辑其实很朴素如果图是稠密图m 接近 n²Floyd 和 Dijkstra 跑 n 次在复杂度上差不多但 Floyd 代码短一个量级肯定选 Floyd如果图是稀疏图m 接近 n且 n 很大跑 n 次 Dijkstra 通常完胜因为 O(n·m) 远小于 O(n³)。Johnson 算法适合“n 大、有负权边、偏稀疏”的折中场景但除非必要我很少在项目里主动用因为实现成本高出 bug 概率大。4.3 顺带一提Warshall 传递闭包和它是一家人Floyd 有个非常著名的近亲——Warshall 算法用于计算传递闭包transitive closure也就是回答“i 能不能通过若干条边到达 j”。它和 Floyd 共享同一个骨架只是把“距离远近”换成了“是否可达”def transitive_closure(n, reach): # reach[i][j] 是布尔值表示 i 能否到达 j 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]这段代码我经常在数据库权限关系推导、依赖关系分析里用到。Floyd 处理“最短路”Warshall 处理“可达性”两个名字绑在一起本质都是同一个“逐轮放行中间节点”的动态规划思路。你理解了 Floyd 的 k 循环Warshall 就是顺手的事。5. 实测中的坑与提速心得骨架写熟之后真正让你头秃的往往是那些不起眼的小问题。我把自己这些年踩过的坑和总结出来的提速招数集中列一下基本覆盖了 Floyd 在实际使用中的高频雷区。5.1 初始化阶段就会犯的三个错第一重边覆盖。前面说过多条同向边必须取最小权不是后读的覆盖先读的。第二点编号从 1 开始。很多算法题习惯把节点编号成 1 到 n你直接套 0 基数组就容易越界或漏点正确做法是数组开到 (n1)×(n1)循环从 1 到 n。第三对角线初始化。dist[i][i]必须为 0但也要注意输入里如果有负的自环i 到 i 的负权边那就直接说明存在负环了算法跑完对角线自然是负数。这三个错我几乎在每次带新人做图论题时都能见到每一条都可能导致 Debug 两小时发现是初始化写错。5.2 Python 版提速招数Python 跑 Floyd 天生吃亏但有几个立竿见影的优化手段跳过不可达行if dist[i][k] INF: continue如果 i 到 k 不可达整行都不用算。局部变量绑定把dist[i]和dist[k]提出来赋值给本地变量row_i、row_k减少二维数组寻址开销。避免在循环里重复计算dist[i][k]先算好base dist[i][k]。对称图只用算一半如果确认图是无向图可以只更新 j ≥ i 的下三角或上三角再对称复制。但这会干扰路径还原的nxt矩阵维护非必要不推荐先保证正确再谈优化。这些优化合起来n500 的 Python 版可以从 8 秒压到 5 秒左右。想再快老实换 C 或 PyPy。5.3 几个实用变种瓶颈路径、必经点、特殊图Floyd 的骨架弹性比看起来大得多改一下松弛条件就能适配不同需求瓶颈路径最大容量路径把min和换成max和min即dist[i][j] max(dist[i][j], min(dist[i][k], dist[k][j]))可以求出“两点之间能使路径上最小边权最大化”的走法。这在水管流量、带宽规划、承重路线场景里很常见。必经点组合先跑一次 Floyd 得到全源距离然后对“必须经过节点集 X”的需求用dist[s][x] dist[x][t]组合查询。这种“预处理 查表”的思路比每次现场跑图快几个数量级。最小换乘次数边权全为 1 的无向图Floyd 跑完直接就是最少换乘数如果节点很多其实 BFS 从每个点跑一遍更快但 Floyd 的代码确实短。我个人在实际项目里的一个体会是Floyd 的价值不在于它快而在于它稳。当你的图规模不大、又需要“任意点对之间某种最优度量”时它的代码量是所有方案里最小的正因为短出 bug 的面也小后期维护的人看一眼就懂。有一回我给一个调度系统做城市间运费预计算数据量只有几十个节点我连 Dijkstra 都没想直接上 Floyd半小时内上线。当然等节点规模真的大了我会毫不犹豫换 Dijkstra 或 Johnson但那是另一个故事了。