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-1，dist 是一个 n×n 的二维矩阵，dist[i][j] 表示当前已知的 i 到 j 的最短距离：
INF = 10 ** 18 def floyd_warshall(n, dist): # dist 是 n x n 矩阵，初始化时： # dist[i][i] = 0，dist[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 权 3
- 0 → 3 权 7
- 1 → 2 权 2
- 1 → 3 权 4
- 2 → 3 权 1
初始矩阵（∞ 表示不可达）：
| i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 3 | ∞ | 7 |
| 1 | 3 | 0 | 2 | 4 |
| 2 | ∞ | 2 | 0 | 1 |
| 3 | 7 | 4 | 1 | 0 |
第 0 轮（k=0，只放行节点 0）：检查以后发现，没有任何一条路径因为经过节点 0 变得更短，矩阵不变。这很正常，因为节点 0 的入度有限。
第 1 轮（k=1，放行节点 1）：重点来了。0 到 2 原来不可达，但 0 → 1 → 2 的代价是 3 + 2 = 5，于是dist[0][2]从 ∞ 变成 5；对称地，2 到 0 也变成 5。
| i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 3 | 5 | 7 |
| 1 | 3 | 0 | 2 | 4 |
| 2 | 5 | 2 | 0 | 1 |
| 3 | 7 | 4 | 1 | 0 |
第 2 轮（k=2，放行节点 2）：0 到 3 原来走直连是 7，现在 0 → 2 → 3 是 5 + 1 = 6，更短，更新；同理 3 到 0 也变成 6。1 到 3 原来是直连 4，现在 1 → 2 → 3 是 2 + 1 = 3，也更新。
第 3 轮（k=3，放行节点 3）：检查所有 i、j 后发现，没有再能压缩的距离。最终矩阵：
| i\j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 3 | 5 | 6 |
| 1 | 3 | 0 | 2 | 3 |
| 2 | 5 | 2 | 0 | 1 |
| 3 | 6 | 3 | 1 | 0 |
注意 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 体感 |
|---|---|---|---|
| 100 | 100 万 | 毫秒级 | 0.1 秒级 |
| 300 | 2700 万 | 0.2 秒左右 | 2 秒左右 |
| 500 | 1.25 亿 | 0.5 秒左右 | 5 到 8 秒 |
| 1000 | 10 亿 | 3 到 5 秒 | 30 秒以上，基本别想 |
以上是粗略量级，跟机器、图密度、是否做了 INF 跳过都有关系，但方向是确定的：n 超过 1000，Python 就该慎重；n 超过 2000，C++ 也要掂量掂量。空间上，n×n 的 long long 矩阵，n=5000 时就是 5000² × 8 字节 ≈ 200MB，已经逼近很多服务的内存红线。
4.2 和“跑 n 次 Dijkstra”的对比
全源最短路径不止 Floyd 一条路。常见对比：
| 方案 | 时间复杂度 | 优势 | 短板 |
|---|---|---|---|
| Floyd | O(n³) | 实现极简，支持负权边 | 只适合小 n 或稠密图 |
| 跑 n 次 Dijkstra | O(n·(m + n log n)) | 稀疏图大杀器 | 不支持负权边，代码复杂 |
| 跑 n 次 Bellman-Ford | O(n²·m) | 支持负权边 | 一般不如 Johnson 实用 |
| Johnson | O(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 基数组就容易越界或漏点，正确做法是数组开到 (n+1)×(n+1)，循环从 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矩阵维护，非必要不推荐，先保证正确再谈优化。
这些优化合起来，n=500 的 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，但那是另一个故事了。
