图系列第 11 篇：Floyd-Warshall——多源最短路

开场：先把前面几篇串起来

欢迎来到图系列第 11 篇。前几篇我们已经把「从一个固定源点出发，到其他所有点的最短路径」这个问题研究得比较透彻：第 8 篇的 BFS 处理无权图，第 9 篇的 Dijkstra 处理边权非负的图，第 10 篇的 Bellman-Ford 第一次把「负权边」这个麻烦家伙请进了屋子，还顺带讲了负环检测。它们有一个共同点：都是单源最短路算法，一次运行只回答「一个源点」的问题。

今天我们要把问题升级：不只要知道从你家出发到各个地方要多久，而是要知道任意两个地方之间的最短距离。这就是所有点对最短路问题，英文叫 All-Pairs Shortest Paths，简称 APSP。主角是 Floyd-Warshall 算法——一个代码短到让人怀疑它是不是真能工作的动态规划算法。它一次运行就把整张距离表全部算出来，允许负权边，能检测负环，稍微改一行还能变成传递闭包算法。有人说它是「图论里性价比最高的十几行代码」，本篇我们就把它彻底讲透。

flowchart TD
    A["第 8 篇：BFS 无权图单源最短路"] --> B["第 9 篇：Dijkstra 非负权单源最短路"]
    B --> C["第 10 篇：Bellman-Ford 负权单源最短路与负环检测"]
    C --> D["第 11 篇：Floyd-Warshall 一次算出所有点对最短路"]

如果你还不太熟悉前面的内容，也不需要慌张。本篇会把动态规划的思路从直觉讲起，不要求你先学过 DP；但建议你对 BFS、Dijkstra、Bellman-Ford 的单源最短路基本框架有个印象，因为我们会频繁拿它们做对比。今天的主角有三个关键词：多源、动态规划、三重循环。抓住这三个词，整篇文章的主线就清楚了。

一、问题：所有点对最短距离

1.1 三个真实场景

场景一：地图公司。假设一家地图公司维护着一张全国高速公路网：城市是节点，道路是边，边权是通行时间或者距离。用户可能在任何一个城市输入任何一个目的地，导航请求到达服务器时，公司希望立刻给出答案。虽然可以等用户问了再现场算一次单源最短路，但如果请求量很大，预先把所有点对的距离算好、存成一张查询表，线上就变成查表操作，快得多。

场景二：社交网络。两个人之间隔了几层朋友关系？把每个用户看成节点，朋友关系看成边，两人之间的距离就是「最短朋友链长度」。平台想做「你可能认识的人」、想度量社区紧密度，常常需要回答大量点对之间的距离问题。对一个小型实验网络，跑所有点对最短路是家常便饭。

场景三：物流与供应链。仓库是节点，运输路线是边，边权是成本。运营者想知道任意两个仓库之间怎么调货最便宜；如果某些路线有补贴或者折扣，边的权重甚至可能是负数——注意，现实里负权边并不像听起来那么荒谬，它可以表示「返利」「补贴」或者「净收益」。

flowchart LR
    A["地图公司：任意两个城市之间的驾车距离"] --> D["想知道所有点对的最短距离"]
    B["社交网络：任意两个人之间的朋友链长度"] --> D
    C["物流网络：任意两个仓库之间的最低运输成本"] --> D
    D --> E["跑 V 次单源算法太贵，或者图里有负权边"]
    E --> F["Floyd-Warshall：一次运行得到整张距离表"]

这三个场景的共同点：我们需要一整张 D[i][j] 距离表，而不是一条从某个固定源点出发的答案。

1.2 朴素做法为什么不够好

最直接的想法是：把单源最短路算法重复跑 V 次，每个节点当一次源点。假设图有 V 个节点、E 条边。

如果边权非负，用堆优化的 Dijkstra，一次运行是 O((V+E) log V)，跑 V 次就是 O(V(V+E) log V)。在稠密图里 E 接近 V 的平方，这个复杂度变成 O(V 的三次方乘 log V)。听着好像还能接受？但对 V 等于 1000 的稠密图，这已经是十亿量级再乘一个对数因子，常数还不小；对于 V 超过 5000 的图，基本不现实。

如果图里有负权边，Dijkstra 直接失效。它的贪心前提是「已经确定最短距离的节点，以后不会被更短的路径更新」，而负权边会打破这一点：一条绕远路可能因为最后一段是负的而整体更短。这时只能每个源点跑一次 Bellman-Ford，一次 O(VE)，V 次就是 O(V 的平方乘 E)。稠密图里 E 是 O(V 的平方)，总复杂度是 O(V 的四次方)，比我们期待的目标慢了一个数量级。

于是我们想要的算法应该满足：一次运行得到全部点对答案；支持负权边（前提是图中没有负环）；复杂度 O(V 的三次方)，而且常数小、代码短、容易调试。Floyd-Warshall 全部满足。

1.3 本篇路线图

本篇的讲解顺序是：先建立「允许经过前 k 个中间点」的 DP 直觉；然后写出递推式，并解释为什么能原地滚动、为什么 k 必须放在最外层循环；接着用一个带负边的四节点图完整手算一遍；再给出 JavaScript/TypeScript 代码与路径还原；最后讨论负环检测、传递闭包、应用场景和算法选型。结尾有要点速查表、七道自测题和下一篇预告。

1.4 距离矩阵的定义与记号约定

在动手之前，先把全篇要用的记号固定下来，后面读起来会顺畅很多。

设图 G 有 V 个节点和 E 条边，节点编号为 0 到 V-1。每条有向边 u → v 带一个权重 w(u, v)，权重可以是负数，但不能有负环。路径的长度是路径上所有边权之和。从 i 到 j 的最短距离记作 d(i, j)，它的定义是「所有从 i 出发、到达 j 的路径的长度最小值」；如果根本不存在这样的路径，d(i, j) 就是无穷大。

全源最短路算法的输出是一张 V 乘 V 的距离矩阵 dist：第 i 行第 j 列就是 d(i, j)。这张矩阵有四个基本性质，可以用来自检。第一，对角线 dist[i][i] 等于 0，因为空路径是合法的，而且无负环时不可能有更短的闭合路径。第二，如果图是无向图，矩阵是对称的，dist[i][j] 等于 dist[j][i]；有向图不一定对称。第三，矩阵满足三角不等式：dist[i][j] 一定不超过 dist[i][k] 加 dist[k][j]，因为右边那条「绕道 k」的路线本身就是一条从 i 到 j 的合法路径。第四，在没有负环时，矩阵里的值都是良定义的实数或无穷大，不会出现「无限减小」的路径。

关于无穷大的记号，正文里统一写作 ∞，代码里对应 JavaScript 的 Infinity。有一点要特别强调：∞ 加任何有限数仍然是 ∞，∞ 加负无穷没有意义，所以我们在算法里从不做「∞ 减 ∞」这类运算，只做加法。只要坚持这个约定，负权边就能安全地参与计算。

另外，本篇讨论的图既包括有向图也包括无向图。无向图的每条边可以看成两条方向相反的有向边，因此 Floyd-Warshall 的代码不需要区分，初始化时把两个方向都填上即可。为了讲解方便，手算示例用的是有向图；传递闭包一节默认也是有向图的可达性，这些细节在对应小节会再次提醒。

二、动态规划的直觉：允许经过前 k 个中间点

2.1 状态设计：给中间节点发「通行证」

Floyd-Warshall 的核心状态定义只有一句话：d[k][i][j] 表示「在只允许把编号为 0 到 k-1 的节点当作中间节点时，从 i 走到 j 的最短路径长度」。

这里的「中间节点」指的是路径上除了起点和终点之外的所有节点。比如路径 0 → 1 → 2 → 3 里，起点是 0，终点是 3，中间节点是 1 和 2。允许把某个节点当作中间节点，意思就是路径可以中途拐进它、再拐出来；起点和终点不受这个限制，它们本来就是路径的两端。

为什么要这样设计状态？因为我们想给「路径的复杂程度」一个可以逐步增加的标尺。最开始时，我们只允许走一条边，也就是不允许任何中间节点；然后每轮多放行一个节点；等到所有节点都被放行，问题就变成了真正的最短路问题。这个「逐步放行」的过程，恰好就是动态规划里最常见的套路：用状态里的一个维度记录规模，用递推从规模小的状态推出规模大的状态。

更具体一点：先把图的 V 个节点随便编上号，比如 0 到 V-1。定义：

d[0][i][j] = 从 i 直接到 j 的边权（没有边就是无穷大，i 等于 j 时是 0）。

这个初始状态非常好算，它根本不需要任何中间节点，一条边直达。然后我们问：如果允许使用节点 0 作为中间节点，答案会变成什么？再问：如果又允许节点 1 呢？……一直问到允许所有节点。第 k 步的状态就是 d[k][i][j]：只允许使用前 k 个节点作为中间节点。

flowchart LR
    I["起点 i"] --> M0["中间点 0"]
    I --> M1["中间点 1"]
    I --> MK["中间点 k-1"]
    M0 --> J["终点 j"]
    M1 --> J
    MK --> J

上图表达的是 d[k][i][j] 的视角：从 i 出发，中间可以任意拐进 0、1、……、k-1 这些节点，最后到达 j。注意这些中间点不一定都要用，也可以用其中一部分，甚至一个都不用。所谓「允许」，是给路径多一种选择，而不是强制要求。

2.2 从 k-1 到 k：多了一个中转城市

现在最关键的问题来了：已知 d[k-1] 这一整层，怎么推出 d[k]？

想象你是一个旅行规划师，之前只能在 A、B、C 这些老城市之间中转，现在城市 K 刚刚开通了中转服务。从 i 城到 j 城，你会怎么规划？无非两种可能。

第一种：我不去 K 城。原来的路线照旧，所有中转都发生在老城市里，长度就是 d[k-1][i][j]。

第二种：我绕道 K 城。那么整条路线可以切成两段：先想办法从 i 城到 K 城，再从 K 城到 j 城。注意，这两段路线内部的中转点仍然只能来自老城市——因为 K 城已经在切点用掉了，如果再在段内出现 K 城，就意味着路径上 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] )

这个式子就是 Floyd-Warshall 的灵魂。它告诉我们：新增一个可用中间点后，任何点对的距离只可能不变，或者因为「绕道新点」而变短，绝不可能变长。

flowchart TD
    A["从 i 到 j 的最短路，允许前 k 个中间点"] --> B["方案一：完全不经过节点 k"]
    A --> C["方案二：绕道节点 k，切成 i 到 k 与 k 到 j 两段"]
    B --> D["候选值 d[k-1][i][j]"]
    C --> E["候选值 d[k-1][i][k] + d[k-1][k][j]"]
    D --> F["取两个候选值中的较小者"]
    E --> F

2.3 为什么最优路径可以「只切一刀」

细心的读者可能会问：如果一条路径经过了节点 k 两次，那把它从 k 处切开，中间那段不是还会包含 k 吗？这样「切成两段，段内只用老节点」的说法还成立吗？

答案是：真正的最优路径不需要重复经过同一个中间节点。我们来严格论证一下。

假设有一条从 i 到 j 的路径，中间某个节点 u 出现了两次。那么从第一次出现 u 到第二次出现 u 之间，路径围成了一个环。现在分三种情况看这个环的权重：

如果环的权重是正数，那么把这段环从路径里删掉，剩下的路径仍然从 i 到 j，而且更短。既然我们讨论的是最短路，这个带正环的路径不可能是最优的。

如果环的权重是零，删掉它不会改变总长度，路径依然是最优的，而且更简洁。

如果环的权重是负数，那就说明图里存在一个负环。负环会让「最短路径」这个概念本身失效：绕着负环多转一圈，总长度还能更小，转无限圈长度就趋近负无穷。Floyd-Warshall 在这样的图上不会给出有意义的距离，但算法运行完可以通过检查对角线发现负环，我们在第六节专门讨论。

所以，只要图里没有负环，就一定存在一条「每个节点至多出现一次」的最优路径。对这样的路径来说，如果它经过节点 k，那么 k 只出现一次，把它从 k 处切开，两段内部都不可能再出现 k；两段内部能用的中间点就只有前 k-1 个。于是 d[k-1][i][k] 和 d[k-1][k][j] 恰好就是这两段的最短长度，拼接起来正好得到一条合法路径。

flowchart LR
    I["i"] --> P1["第一段：内部只能用前 k-1 个节点"] --> K["k"]
    K --> P2["第二段：内部只能用前 k-1 个节点"] --> J["j"]

这个论证同时解释了为什么递推式里的下标都是 k-1 而不是 k：两段路径都不能再把 k 当作内部中转，否则就会把「绕道 k」这件事做两遍，而最优路径不需要做两遍。

2.4 直觉总结

把这一节的直觉压缩成一句话：Floyd-Warshall 是「逐步放行中间节点」的算法。第 k 轮相当于宣布节点 k 可以当中转了，然后对所有点对问一句：绕道 k 会不会更短？会，就更新；不会，就保持原样。

这个思想在生活中也很常见：以前没有高铁站的城市之间只能走老路，新高铁站开通后，凡是「先到新站、再从新站出发」能缩短的路程都会被替换掉。等所有城市都开通了中转服务，全图的最短距离表自然就成形了。

2.5 用具体数字感受状态维度

「d[k][i][j] 是第 k 层的值」这句话听起来抽象，我们用第四节示例图里的两个格子，把每一层的数值变化列出来，感受一下状态维度到底在记录什么。

先看 0 到 2 这个点对。初始时只有直达边，d[0][0][2] 等于 10。第 1 轮放行节点 0，但 1 还没有被放行，绕道节点 0 并不能改善 0 到 2，所以 d[1][0][2] 还是 10。第 2 轮放行节点 1，出现了候选路径 0 → 1 → 2，长度是 3 加负 2 等于 1，于是 d[2][0][2] 变成 1。第 3 轮放行节点 2 之后，0 到 2 再没有更短的绕法，d[3][0][2] 保持 1，最终答案也是 1。

再看 1 到 0 这个点对。初始时没有直达边，也没有任何中间点可用，d[0][1][0] 是 ∞。前两轮放行节点 0 和 1 都没能让它变成有限值。第 3 轮放行节点 2 后，候选路径 1 → 2 → 0 出现了，长度是负 2 加 1 等于负 1，d[3][1][0] 变成负 1，这就是最终答案。

这两个例子展示了状态维度 k 的语义：它不是一个「轮数编号」这么简单，而是「允许使用的中间节点集合的大小」。随着 k 增大，集合扩大，每个格子的值只可能变小或者不变。把三层数组按 k 轴展开，你会看到每一层都是上一层「多放行一个节点」之后的结果。这个「层层递进、只减不增」的画面，就是 Floyd-Warshall 全部正确性的来源。

也正因如此，动态规划的三个要素——状态、边界、递推——在这里一目了然：状态是 d[k][i][j]，边界是 k 等于 0 时的邻接矩阵，递推是「绕道新节点取 min」。如果你以前没学过 DP，可以把这套三要素当作模板记下来：任何动态规划题，先问自己状态是什么、边界是什么、怎么从小状态推到大状态。

三、递推式与原地滚动：为什么 k 必须是最外层

3.1 完整递推式

把上一节的讨论整理成标准记号。设图有 n 个节点，编号从 0 到 n-1，w[i][j] 表示从 i 到 j 的边权，没有边时记作无穷大，规定 w[i][i] = 0。定义 d[k][i][j] 为「只允许使用节点 0 到 k-1 作为中间节点时，i 到 j 的最短路径长度」，其中 k 的取值范围是 0 到 n。

边界条件：

d[0][i][j] = w[i][j]

递推关系：

d[k][i][j] = min( d[k-1][i][j], d[k-1][i][k-1] + d[k-1][k-1][j] )

注意这里第 k 层新放行的节点编号是 k-1，因为前 k 个节点是 0 到 k-1。很多教材会直接用「d[k][i][j] 表示允许经过节点 1 到 k」，写法略有差异，但本质完全一样。为了避免下标绕晕，下面写代码时我们统一用「第 k 轮放行节点 k」的说法，也就是把节点编号和轮数对齐，递推写成：

d[k][i][j] = min( d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j] )

最终答案存在 d[n][i][j]：所有 n 个节点都被允许作为中间节点，这就是真正的全源最短路距离矩阵。

3.2 三维数组看起来很费空间

如果照搬定义，我们需要一个 n 乘 n 乘 (n+1) 的三维数组，空间复杂度 O(n 的三次方)。n 等于 500 时就是一亿多个数，虽然现代机器未必装不下，但完全没有必要。

观察递推式：第 k 层的每一个格子 d[k][i][j] 只依赖第 k-1 层的三个格子：d[k-1][i][j]、d[k-1][i][k]、d[k-1][k][j]。也就是说，我们只需要保留「上一层」的数据，用完一层就把它覆盖成当前层，和滚动数组的思路一模一样。于是可以只用一个二维矩阵 dist[i][j] 原地更新：

for k = 0 到 n-1： 对每一对 (i, j)： dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

这就是大家熟悉的 Floyd-Warshall 三重循环。第一眼看到这段代码的人往往有两个疑问：为什么可以原地覆盖？为什么 k 必须是最外层循环？下面我们把这两个问题彻底讲清楚。

3.3 为什么可以原地覆盖

原地覆盖要求一个关键性质：在第 k 轮计算 dist[i][j] 时，等号右边用到的 dist[i][k] 和 dist[k][j] 必须仍然是「第 k 轮开始前」的值，也就是 d[k-1] 层的值，而不能已经被本轮更新成 d[k] 层的值。

这听起来很危险，因为第 k 轮确实会更新很多格子，dist[i][k] 和 dist[k][j] 也属于可能被更新的格子。为什么它们不会被更新成更小的值呢？

关键在于：第 k 轮的所有更新，全部是以节点 k 作为中转的更新。请看 dist[i][k] 的更新公式：

dist[i][k] = min( dist[i][k], dist[i][k] + dist[k][k] )

如果 dist[k][k] 大于等于 0，那么 dist[i][k] + dist[k][k] 不会小于 dist[i][k]，取 min 之后 dist[i][k] 保持不变。而 dist[k][k] 在无负环的图里正好大于等于 0：从 k 出发回到 k 的最短路径，最短也就是空路径，长度为 0；如果存在负的闭合路径，那本身就是负环的信号，会在检测阶段被揪出来。同理，dist[k][j] 的更新是：

dist[k][j] = min( dist[k][j], dist[k][k] + dist[k][j] )

同样不会变小。所以整个第 k 轮里，dist[i][k] 和 dist[k][j] 这两个「中转参考值」始终保持在第 k 轮开始时的状态。原地覆盖是安全的。

一个自然的推论：第 k 轮结束后的矩阵，正是 d[k] 层的完整结果。每一轮都在旧矩阵上「盖」出新矩阵，旧的 d[k-1] 层除了被读取过，不再需要保留。

flowchart TD
    A["第 k 轮：放行节点 k 作为中转"] --> B["需要读 dist[i][k] 与 dist[k][j]"]
    B --> C["这两个值在本轮不会变小"]
    C --> D["因为 dist[k][k] 大于等于 0"]
    D --> E["dist[i][k] 与 dist[k][j] 保持为上一轮的值"]
    E --> F["所有 dist[i][j] 可以用旧值安全更新"]
    F --> G["本轮结束，矩阵整体变成 d[k] 层"]

3.4 为什么 k 必须放在最外层

理解了原地覆盖的原理，循环顺序的问题就顺理成章了。如果 k 在最外层，那么每一轮我们只放行一个新节点 k，矩阵从 d[0] 层逐步推进到 d[n] 层，语义完全对应递推式。

假如把 k 放到内层，比如写成 i 在最外层、k 在中间、j 在最内层，会发生什么？当我们在处理某个固定的 i 时，内层循环会依次放行节点 0、1、2、……。刚放行节点 0 得到的更新结果，立刻会被放行节点 1 时用到；也就是说，同一个 i 的行里，我们同时混合了「允许前 0 个节点」「允许前 1 个节点」「允许前 2 个节点」等多个阶段的状态，递推的层次感被破坏了。

这听起来可能只是「不优雅」，但实际上是错误。Floyd-Warshall 的正确性依赖严格的两阶段结构：计算第 k 层时，中转参考值必须来自第 k-1 层。把 k 放内层会让「某个点对先借新节点 k 更新，再借更晚的节点」这种跨阶段组合悄悄发生，某些本该成立的更短路径会因为更新顺序不对而漏掉，最终结果可能不是真正的最短路。

至于 i 和 j 的顺序，则无关紧要。因为第 k 轮里所有更新都只依赖不会变化的 dist[i][k] 和 dist[k][j]，不管先更新哪一行哪一列，读到的中转参考值都一样。所以只要 k 在最外层，i、j 随便嵌套都正确。

flowchart TD
    A["for k = 0 到 n-1"] --> B["for i = 0 到 n-1"]
    B --> C["for j = 0 到 n-1"]
    C --> D["dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])"]
    D --> C
    C --> E["j 循环结束"]
    E --> B
    B --> F["i 循环结束"]
    F --> A
    A --> G["k 循环结束，dist 就是最终答案"]

3.5 一个小实验帮助记忆

如果你以后忘了循环顺序，可以用这个记忆锚点：Floyd-Warshall 的每一轮讨论的主角是「节点 k」，所有更新都在问「绕道 k 是否更短」。既然是「按节点轮次推进」，k 自然应该是最外层的时钟。先有轮次，再有轮次内部的全面检查，逻辑才顺。

另外还有一个非常实用的记忆技巧：把三重循环写成「k-i-j」的口诀。很多面试者在手写代码时容易把顺序写成 i-k-j 或者 i-j-k，结果在带负权的图上得到错误答案。养成先写 k 的习惯，能帮你避开这个经典陷阱。

3.6 为什么最优路径最多只需要 V-1 条边

这一小节回答一个和正确性密切相关的问题：Floyd-Warshall 为什么跑 n 轮就够？会不会存在一条最短路径，中间节点多到需要「放行」超过 n 轮？

答案是不会。我们之前论证过：只要图里没有负环，就存在一条不重复经过任何节点的最短路径。一条不重复经过任何节点的路径，最多只能经过 V 个不同的节点，也就是最多有 V-1 条边。理由非常朴素：路径上每一条边都会引入一个新的、没有出现过的节点；如果边数达到 V，按照抽屉原理，V 条边会把 V 个节点全部用掉，但一条有 V 条边的路径有 V+1 个位置，必然有某个节点重复出现，就形成了环。所以无环路径的边数上限就是 V-1。

这个结论其实和 Bellman-Ford 是同一个故事的两种讲法。Bellman-Ford 的状态维度是「路径最多用几条边」，它做 V-1 轮松弛，每一轮把允许的边数上限加一，正好覆盖所有无环路径；Floyd-Warshall 的状态维度是「允许使用哪些中间节点」，它做 V 轮放行，每轮把允许的中间节点集合扩大一个，也正好覆盖所有无环路径。一个按边数切，一个按节点集合切，殊途同归。

理解这一点还有一个实际用途：当你在分析复杂度时，可以理直气壮地说 Floyd-Warshall 的 V 轮是「充分」的，而不是「碰巧够用」。任何声称「需要超过 V 轮」的最短路，必然绕了环；绕环要么没好处，要么说明有负环。

3.7 邻接矩阵与图的输入形式

Floyd-Warshall 天然以邻接矩阵为输入，这也是它和 Dijkstra、Bellman-Ford 的一个显著区别。后两者常用邻接表，因为每次松弛只看一条边的两个端点；Floyd 每一轮要枚举所有点对，矩阵的下标访问最方便，复杂度 O(V 的三次方) 也和边数无关。

如果业务数据原本是边列表，要先转换成矩阵：初始化一个 n 乘 n 的矩阵，对角线填 0，其余填 Infinity，然后对每条边 u 到 v 权重 w，执行 dist[u][v] = min(dist[u][v], w)。注意用 min 而不是直接赋值，因为输入里可能有重边，保留权重最小的那条。

还有一个容易被忽略的细节：无向图可以看成两条方向相反的有向边，所以初始化时要把 u 到 v 和 v 到 u 都填上；有向图则只填一条。Floyd-Warshall 对无向图和有向图都适用，代码不需要任何区别，只是输入矩阵的对称性不同。无向图的距离矩阵最终一定是对称的，这也是一个很实用的自检方法：跑完发现不对称，说明初始化或更新有 bug。

另外，矩阵里的对角线一定要初始化为 0。有些新手会把对角线也填成 Infinity，结果任何「绕道自己」的候选都会被错误地排除，全源距离全错。初始化矩阵时，先统一填 0 和 Infinity，再覆盖边权，是最不容易出错的做法。

四、完整手算：一个带负边的四节点图

理论讲得再多，不如亲手算一遍。这一节我们用一张包含负权边、但不存在负环的四节点图，把 Floyd-Warshall 的每一轮矩阵变化完整走一遍。请准备一张纸，跟着表格自己推一遍，理解会深很多。

4.1 示例图与初始矩阵

图里有四个节点：0、1、2、3。边如下：

0 → 1，权重 3

0 → 2，权重 10

1 → 2，权重 -2

1 → 3，权重 7

2 → 3，权重 4

2 → 0，权重 1

3 → 1，权重 2

flowchart LR
    A["0"] -->|"3"| B["1"]
    A -->|"10"| C["2"]
    B -->|"-2"| C
    B -->|"7"| D["3"]
    C -->|"4"| D
    C -->|"1"| A
    D -->|"2"| B

注意这里有一个负权边：1 → 2 的权重是 -2。它会让 Dijkstra 失效，但对 Floyd-Warshall 没有任何问题。再检查一下有没有负环：0 → 1 → 2 → 0 的总权重是 3 加负 2 加 1，等于 2，是正数；1 → 3 → 1 的总权重是 7 加 2，等于 9；其他环也都是正的。所以这是一个无负环图，适合做手算。

初始矩阵 d[0] 就是邻接矩阵：dist[i][j] 等于边权，没有边记作 ∞，对角线是 0。

dist	0	1	2	3
0	0	3	10	∞
1	∞	0	-2	7
2	1	∞	0	4
3	∞	2	∞	0

约定：以后每一轮表格里，我们把「本轮发生变化的格子」加粗标出，方便对照。

4.2 第 0 轮：放行节点 0

这一轮所有更新都走「绕道节点 0」这条候选。逐项检查：

先看 1 → 2。原值是 -2。候选路径 1 → 0 → 2 的长度是 dist[1][0] 加 dist[0][2]，也就是 ∞ 加 10，仍然是 ∞，不可能比 -2 更短，保持 -2。

再看 2 → 1。原值是 ∞。候选路径 2 → 0 → 1 的长度是 1 加 3，等于 4，比 ∞ 小，更新为 4。

接着看 2 → 3。原值是 4。候选路径 2 → 0 → 3 的长度是 1 加 ∞，仍然是 ∞，保持 4。

看 1 → 3。原值是 7。候选路径 1 → 0 → 3 的长度是 ∞ 加 ∞，保持 7。

看 3 → 1。原值是 2。候选路径 3 → 0 → 1 的长度是 ∞ 加 3，保持 2。

看 3 → 2。原值是 ∞。候选路径 3 → 0 → 2 的长度是 ∞ 加 10，保持 ∞。

第 0 轮结束后，只有 2 → 1 从 ∞ 变成了 4：

dist	0	1	2	3
0	0	3	10	∞
1	∞	0	-2	7
2	1	4	0	4
3	∞	2	∞	0

4.3 第 1 轮：放行节点 1

这一轮所有更新都尝试绕道节点 1。我们挑几个有代表性的格子算。

0 → 2。原值是 10。候选路径 0 → 1 → 2 的长度是 dist[0][1] 加 dist[1][2]，也就是 3 加负 2，等于 1。1 比 10 小，更新为 1。这条路径正是利用负权边得到的好消息：0 先到 1，再从 1 走负权边到 2，总共只要 1，比直达的 10 短得多。

0 → 3。原值是 ∞。候选路径 0 → 1 → 3 的长度是 3 加 7，等于 10。更新为 10。

2 → 3。原值是 4。候选路径 2 → 1 → 3 的长度是 dist[2][1] 加 dist[1][3]，即 4 加 7，等于 11，比 4 大，保持 4。

3 → 2。原值是 ∞。候选路径 3 → 1 → 2 的长度是 dist[3][1] 加 dist[1][2]，即 2 加负 2，等于 0。0 比 ∞ 小，更新为 0。注意这里出现了零长度的非空路径：3 先到 1，再顺着负权边到 2，总长正好是 0。

3 → 0。原值是 ∞。候选路径 3 → 1 → 0 的长度是 2 加 ∞，保持 ∞。

2 → 0。原值是 1。候选路径 2 → 1 → 0 的长度是 4 加 ∞，保持 1。

第 1 轮结束后：

dist	0	1	2	3
0	0	3	1	10
1	∞	0	-2	7
2	1	4	0	4
3	∞	2	0	0

4.4 第 2 轮：放行节点 2

这一轮开始，图里的负权边真正显身手了，因为节点 2 现在可以当中转，而进入节点 2 的边是负的。

0 → 3。原值是 10。候选路径 0 → 2 → 3 的长度是 dist[0][2] 加 dist[2][3]，即 1 加 4，等于 5。5 比 10 小，更新为 5。这条路径的完整走法是 0 → 1 → 2 → 3，权重 3 加负 2 加 4。

1 → 0。原值是 ∞。候选路径 1 → 2 → 0 的长度是 dist[1][2] 加 dist[2][0]，即负 2 加 1，等于负 1。负 1 比 ∞ 小，更新为负 1。这是一个非常经典的负权案例：1 走负权边到 2，再走边 2 → 0，总长度竟然只有负 1，比任何「直接或绕别的路」都短。

1 → 3。原值是 7。候选路径 1 → 2 → 3 的长度是负 2 加 4，等于 2。更新为 2。

3 → 0。原值是 ∞。候选路径 3 → 2 → 0 的长度是 dist[3][2] 加 dist[2][0]，即 0 加 1，等于 1。更新为 1。

3 → 1。原值是 2。候选路径 3 → 2 → 1 的长度是 0 加 4，等于 4，比 2 大，保持 2。

0 → 1。原值是 3。候选路径 0 → 2 → 1 的长度是 1 加 4，等于 5，保持 3。

0 → 2。原值是 1。候选路径 0 → 2 → 2 的长度是 1 加 0，等于 1，保持 1。

第 2 轮结束后：

dist	0	1	2	3
0	0	3	1	5
1	-1	0	-2	2
2	1	4	0	4
3	1	2	0	0

4.5 第 3 轮：放行节点 3

最后一轮放行节点 3。逐个候选检查：

0 → 1。原值是 3。候选路径 0 → 3 → 1 的长度是 5 加 2，等于 7，保持 3。

0 → 2。原值是 1。候选路径 0 → 3 → 2 的长度是 5 加 0，等于 5，保持 1。

1 → 0。原值是负 1。候选路径 1 → 3 → 0 的长度是 2 加 1，等于 3，保持负 1。

1 → 2。原值是负 2。候选路径 1 → 3 → 2 的长度是 2 加 0，等于 2，保持负 2。

2 → 0。原值是 1。候选路径 2 → 3 → 0 的长度是 4 加 1，等于 5，保持 1。

2 → 1。原值是 4。候选路径 2 → 3 → 1 的长度是 4 加 2，等于 6，保持 4。

2 → 3。原值是 4。候选路径 2 → 3 → 3 的长度是 4 加 0，保持 4。

这一轮没有任何更新，最终矩阵和第 2 轮结束后的矩阵完全一样：

dist	0	1	2	3
0	0	3	1	5
1	-1	0	-2	2
2	1	4	0	4
3	1	2	0	0

4.6 结果验证

最终矩阵就是所有点对的最短距离。挑几个验证：

0 到 3 的距离是 5，对应路径 0 → 1 → 2 → 3，权重 3 加负 2 加 4 等于 5。直接走 0 → 3 根本无边，走 0 → 1 → 3 是 10，都不如这条绕路的组合短。

1 到 0 的距离是负 1，对应路径 1 → 2 → 0，权重负 2 加 1 等于负 1。这就是负权边的魅力：最短路径的总长可以是负数，只要路径本身不含负环就行。

3 到 2 的距离是 0，对应路径 3 → 1 → 2，权重 2 加负 2 等于 0。注意它不是空路径，却和空路径一样长，说明图上存在零权环路的可能性；这不妨碍算法，min 会自然保留 0。

4.7 矩阵变化总览

把四轮矩阵串起来看，就像看一部电影：每一帧只做一件事，就是尝试「绕道新放行的节点」，能缩短就缩短。下面这张图浓缩了整个变化过程：

flowchart LR
    M0["初始矩阵<br/>0 3 10 ∞<br/>∞ 0 -2 7<br/>1 ∞ 0 4<br/>∞ 2 ∞ 0"] --> M1["放行节点 0 后<br/>0 3 10 ∞<br/>∞ 0 -2 7<br/>1 4 0 4<br/>∞ 2 ∞ 0"]
    M1 --> M2["放行节点 1 后<br/>0 3 1 10<br/>∞ 0 -2 7<br/>1 4 0 4<br/>∞ 2 0 0"]
    M2 --> M3["放行节点 2 后<br/>0 3 1 5<br/>-1 0 -2 2<br/>1 4 0 4<br/>1 2 0 0"]
    M3 --> M4["放行节点 3 后<br/>0 3 1 5<br/>-1 0 -2 2<br/>1 4 0 4<br/>1 2 0 0"]

请特别注意第二帧到第三帧的变化：正是节点 1 的负权入边让 0 → 2 从 10 缩到 1，也是节点 2 的负权出边让 1 → 0 变成负 1。负权边并不可怕，只要没有负环，Floyd-Warshall 都能稳稳地处理。

4.8 手算时的常见错误与查错技巧

跟着手算走一遍是理解 Floyd-Warshall 最好的方式，但第一次手算时很容易踩几个经典的坑，这里提前帮你排一排。

第一个坑：忘记对角线是 0。初始矩阵里 dist[i][i] 必须填 0，否则「绕道自己」的候选会变成无穷大加无穷大，很多本应更新的格子会漏掉。

第二个坑：把无穷大写成一个很大的有限数，比如 999999。如果图里出现负权边，999999 加负 5 还是 999994，看起来「更新」了，但更新出来的根本不是真实路径。手算时用 ∞ 符号，代码里用真正的 Infinity，能避免这类假更新。

第三个坑：在第 k 轮里使用了「本轮刚更新出来的 dist[i][k] 或 dist[k][j]」。手算时如果不小心拿 k=1 轮的新值去算 k=1 轮的另一个格子，就会混入下一层的状态。解决办法是时刻提醒自己：每一轮只围绕「放行的那个新节点」做中转，中转参考值永远取自上一轮。

第四个坑：只盯着一行看，忘了列。比如检查「0 到 3 还能不能更短」时，候选路径可能从 0 到某个中间点、再跳到 3，中间点的行和列都要查。手算时逐格对照「绕道新节点」两个值，是最稳妥的。

查错的技巧也很简单：每轮结束后，把矩阵里变化的格子圈出来，确认每个变化的格子都是因为「绕道本轮新放行的节点」而变短；如果有格子变了但绕道路径反而更长，说明算错了。另外可以用「距离矩阵每轮只减不增」这个性质做全局自检：任何一轮如果出现了某个格子变大，一定是写错了。

4.9 如果再加一个节点：增量扩展的思考

假设在示例图上新增节点 4，并加上两条边：4 → 0 权重 2，4 → 3 权重 1。其他结构不变。Floyd-Warshall 只需要把矩阵扩成 5 乘 5，然后继续跑 k 等于 4 的那一轮即可；前四轮的结果全部可以复用。

新的节点会带来什么变化？以 4 到 2 为例：候选路径 4 → 3 → 1 → 2 的权重是 1 加 2 加负 2，等于 1；候选路径 4 → 0 → 1 → 2 的权重是 2 加 3 加负 2，等于 3；所以 dist[4][2] 最终是 1。再看 4 到 1：4 → 3 → 1 是 1 加 2 等于 3，4 → 0 → 1 是 2 加 3 等于 5，最终是 3。这个练习说明：新增节点只会增加一轮计算，已有节点之间的距离永远不会因为新节点加入而变差。

这个「增量友好」的性质在工程上很有价值。比如地图公司每周新增一批城市或道路，如果图规模不大，可以直接在旧矩阵上追加行和列，再补跑一轮，而不必从头算起。当然，如果增删频繁，维护全源矩阵的成本依然高昂，那时就要考虑别的策略了；但在「预计算 + 低频更新」的架构里，Floyd-Warshall 的增量能力是一个实实在在的优点。

4.10 如果改用 Dijkstra 会怎样

为了理解为什么全源问题不能简单用「V 次 Dijkstra」解决，这里专门构造一个三节点小图，看看 Dijkstra 在负权边上是怎么翻车的。

图的结构：0 → 1 权重 1，0 → 2 权重 0，1 → 2 权重负 2。没有负环，但存在一条负权边 1 → 2。

flowchart LR
    A["0"] -->|"1"| B["1"]
    A -->|"0"| C["2"]
    B -->|"-2"| C

从源点 0 跑 Dijkstra。初始 dist[0] 等于 0，其余都是无穷。第一步扩展 0，把 dist[1] 更新成 1，dist[2] 更新成 0。接下来从未确定的节点里挑距离最小的：dist[2] 是 0，dist[1] 是 1，于是节点 2 被「确定」，从此不再访问。

然后扩展节点 1，发现从 0 到 1 再到 2 的总长度是 1 加负 2，等于负 1，比 dist[2] 的 0 更小。但节点 2 已经被确定，Dijkstra 的贪心保证「确定过的节点不可能再被更新」，所以这个负 1 被无视。最终算法给出 dist[0][2] 等于 0，而正确答案是负 1。这就是 Dijkstra 在负权图上的经典失败：它过早地确定了节点 2，而一条绕远路加上负权边，反而比直达更短。

回到第四节那张四节点图，如果对每个源点各跑一次 Dijkstra，运气好的话某些源点的结果碰巧正确，但没有任何保证。负权边的存在让「贪心确定」变得不可靠，而 Floyd-Warshall 的 DP 递推从设计上就避免了这个问题：它不提前确定任何点，每一轮都在全矩阵上比较「绕道新节点」的候选，直到所有中间点都放行完毕。

这个对比值得反复体会：Dijkstra 的快建立在贪心成立的前提上，Floyd 的稳建立在枚举所有中间点组合的前提上。一个追求速度，一个追求全面，适用的图条件自然不同。

4.11 手算之后：学会读最终矩阵

四轮手算结束，最终矩阵已经拿到。但「算出来」和「读懂」是两回事，这里教三个读矩阵的技巧，以后看到任何全源距离矩阵都能用。

第一个技巧：按行读，按列读。第 i 行告诉我们「从 i 出发能到哪些节点、各要多远」，是 i 视角的导航表；第 j 列告诉我们「谁能到达 j、各要多远」，是 j 视角的到达表。很多图论指标，比如「从某个节点出发最远要多久」，就是取这一行的最大值；「到达某个节点最快从哪来」，就是找这一列的最小值。

第二个技巧：用三角不等式自检。对任意三个节点 i、j、k，dist[i][j] 一定不大于 dist[i][k] 加 dist[k][j]。如果发现某个格子违反了这个不等式，说明矩阵算错了。这个性质也可以用来做面试中的快速验算：随手挑三个节点，口算一下绕道路径，看看和矩阵值是否吻合。

第三个技巧：区分「不可达」和「距离很大」。矩阵里保留 ∞ 的格子代表从 i 到 j 根本没有路径，而不是距离特别大。有些业务场景需要把 ∞ 映射成「无法服务」，有些场景则要求排除这些点对再算直径、平均值等统计量。处理时务必先过滤，否则统计结果会被无穷大污染。

读矩阵这件事看似简单，却是全源算法落地时最常出 bug 的环节：算对了、读错了，等于白算。养成「行列分清、过滤无穷、三角校验」三个习惯，能省掉大量排错时间。

五、代码实现：三重循环与路径还原

5.1 基础版：只需要距离

把前面的递推式翻译成 JavaScript/TypeScript，就是下面这段。输入是一个 n 乘 n 的邻接矩阵 graph，graph[i][j] 是从 i 到 j 的边权；没有边的地方用 Infinity，对角线为 0。

function floydWarshall(graph: number[][]): number[][] {
  const n = graph.length;
  const dist = graph.map((row) => row.slice());

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        const viaK = dist[i][k] + dist[k][j];
        if (viaK < dist[i][j]) {
          dist[i][j] = viaK;
        }
      }
    }
  }

  return dist;
}

逐行解释：

第一行到第三行：拿到节点数 n，然后把输入的邻接矩阵深拷贝到 dist 里。深拷贝很重要，因为算法会原地修改矩阵，如果你直接复用 graph，调用方的数据会被破坏。这里用 map 加 slice 复制每一行。

外层循环 for (let k = 0; k < n; k++)：第 k 轮放行节点 k。正如第三节强调的，k 必须是最外层，这是整个算法的时钟。

中间循环 for (let i = 0; i < n; i++)：遍历所有起点。

中间循环里的剪枝：如果 dist[i][k] 是 Infinity，说明从 i 根本到不了 k，那么任何「先到 k 再出发」的路径都不存在，直接跳过这一行，节省一点时间。这个剪枝不影响正确性，只是避免无意义的加法。

内层循环 for (let j = 0; j < n; j++)：遍历所有终点。

更新语句：计算绕道 k 的候选长度 dist[i][k] + dist[k][j]，如果比当前值小，就更新 dist[i][j]。注意等号右边的 dist[i][k] 和 dist[k][j] 在第 k 轮内不会变小，这正是原地更新的安全保证。

函数返回 dist。运行结束后，dist[i][j] 就是从 i 到 j 的最短路径长度。如果在结果矩阵的对角线上发现负数，说明图里有负环，结果不可信。

5.2 路径还原：next 矩阵

很多时候我们不仅要最短距离，还要最短路径本身：导航要给出具体路线，物流要给出具体中转方案。Floyd-Warshall 可以用一个额外的 next 矩阵记录路径。

next[i][j] 表示「从 i 到 j 的最短路径上，i 之后的第一个节点是谁」。初始时，如果 i 到 j 有直达边，next[i][j] = j；如果没有边，记作 -1 表示不可达。对角线 next[i][i] = i。

在更新 dist[i][j] 的同一个 if 里，同时更新 next[i][j] = next[i][k]。为什么是这个值而不是 k？因为新路径先走「从 i 到 k 的最短路径」，再走「从 k 到 j 的最短路径」；从 i 出发的第一步，由第一段路径决定，而第一段路径上 i 的下一个节点正是 next[i][k]。如果直接写成 k，那么当 i 到 k 的最短路径还要经过别的中间节点时，路径记录就丢了。

function floydWarshallWithPath(graph: number[][]): { dist: number[][]; next: number[][] } {
  const n = graph.length;
  const dist = graph.map((row) => row.slice());
  const next = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) =>
      Number.isFinite(dist[i][j]) ? j : -1
    )
  );

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        const viaK = dist[i][k] + dist[k][j];
        if (viaK < dist[i][j]) {
          dist[i][j] = viaK;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  return { dist, next };
}

function reconstructPath(next: number[][], start: number, end: number): number[] | null {
  if (next[start][end] === -1) return null;

  const path: number[] = [start];
  let current = start;
  while (current !== end) {
    current = next[current][end];
    path.push(current);
  }
  return path;
}

reconstructPath 的逻辑也很简单：从 start 出发，不断查「从当前节点到 end 的下一个节点是谁」，沿着 next 链走到 end 为止。如果 next[start][end] 是 -1，说明 start 到 end 不可达，返回 null。

拿第四节手算的图举例。最终 next 矩阵里，next[0][3] = 1（0 到 3 的最短路第一步去 1），next[1][3] = 2（1 到 3 的最短路第一步去 2），next[2][3] = 3（2 到 3 直达）。沿着链走：0 → 1 → 2 → 3，正好是那条权重为 5 的最短路径。

flowchart LR
    A["0"] -->|"next[0][3] = 1"| B["1"]
    B -->|"next[1][3] = 2"| C["2"]
    C -->|"next[2][3] = 3"| D["3"]

再举一个带中转的例子：1 到 0 的最短路第一步是 next[1][0] = 2，即先到 2；而 2 到 0 直达，next[2][0] = 0。拼起来就是 1 → 2 → 0，总长负 1。next 矩阵把整张图的最短路径森林都编码在里面，任何点对都可以 O(路径长度) 地还原出来。

5.3 复杂度分析

时间上，三重循环每一层都遍历 n 次，总共执行 n 的三次方次更新，时间复杂度是 O(n 的三次方)，也就是 O(V 的三次方)。这是 Floyd-Warshall 最突出的特征：与边数无关，只与节点数有关。

空间上，dist 矩阵是 O(V 的平方)；如果还要路径还原，next 矩阵再占 O(V 的平方)。两个矩阵加起来还是 O(V 的平方)。

对比一下：对稠密图（E 接近 V 的平方）跑 V 次堆优化 Dijkstra 是 O(V 的三次方 log V)，Floyd 的常数小得多，代码也短得多；对稀疏图，Dijkstra 跑 V 次是 O(VE log V) 量级，可能比 Floyd 更快，这时选型要看图的密度，第八节会给出总结表。

5.4 无穷大的处理技巧

实现时最常见的坑是无穷大。JavaScript 里用 Number.POSITIVE_INFINITY 非常方便：Infinity 加任何有限数还是 Infinity，Infinity 和负数相加还是 Infinity，所以不用额外判断加法溢出。唯一要注意的是别把无穷大表示成 1e9 这种「很大的有限数」：如果图中边的数量级也很大，dist[i][k] + dist[k][j] 可能超过 1e9，造成假更新。

如果语言不支持可靠的浮点无穷大，可以用一个足够大的常量 INF，比如 10 的 15 次方，并且更新时先判断 dist[i][k] 是否等于 INF。另外，加法里如果出现 INF 加负数，有些语言的整数溢出可能变成很小的数，务必显式跳过不可达的源点。

5.5 关于循环变量 i 和 j 的小优化

细心的读者可能发现，当 i 等于 k 或者 j 等于 k 时，更新公式没有意义：dist[k][j] = min(dist[k][j], dist[k][k] + dist[k][j])，只要 dist[k][k] 不小于 0 就不会变。所以可以跳过这些格子，省下大约 n 的平方量级的无用操作。不过它们不影响正确性，为了代码简洁，多数实现保留完整循环。面试时如果你能主动提到这个细节，会加分。

5.6 用 next 矩阵完整还原一遍示例

还是第四节那张四节点图，我们看看 next 矩阵是怎么跟着 dist 一起演化的。初始时，凡是存在直接边的点对，next[i][j] 等于 j；没有直接边的点对是 -1；对角线 next[i][i] 等于 i。

所以初始 next 矩阵是：

next	0	1	2	3
0	0	1	2	-1
1	-1	1	2	3
2	0	-1	2	3
3	-1	1	-1	3

第 1 轮放行节点 1 时，0 → 2 更新为 1，对应的 next[0][2] 变成 next[0][1]，也就是 1。含义很直观：新的最短路径 0 → 1 → 2 的第一步是去 1，而不是像原来那样直接去 2。同一轮，3 → 2 更新为 0，next[3][2] 变成 next[3][1]，也就是 1，表示新路径 3 → 1 → 2 的第一步去 1。

第 2 轮放行节点 2 时，0 → 3 更新为 5，next[0][3] 变成 next[0][2]，此时 next[0][2] 已经是 1，所以第一步仍然是去 1。1 → 0 更新为负 1，next[1][0] 变成 next[1][2]，也就是 2。1 → 3 更新为 2，next[1][3] 变成 next[1][2]，也就是 2。3 → 0 更新为 1，next[3][0] 变成 next[3][2]，而 next[3][2] 是 1，所以第一步去 1。

最终 next 矩阵如下：

next	0	1	2	3
0	0	1	1	1
1	2	1	2	2
2	0	1	2	3
3	1	1	1	3

用 reconstructPath 还原 1 到 3：从 1 出发，next[1][3] 是 2，走到 2；再看 next[2][3] 是 3，走到 3；路径是 1 → 2 → 3，权重负 2 加 4 等于 2，和 dist[1][3] 一致。还原 3 到 0：next[3][0] 是 1，next[1][0] 是 2，next[2][0] 是 0，路径是 3 → 1 → 2 → 0，权重 2 加负 2 加 1 等于 1，也和 dist[3][0] 一致。每一步都能对上，说明 next 维护正确。

5.7 常见实现错误清单

把新手最常犯的错误集中列出来，写完代码后逐条对照检查，能省下大量调试时间。

第一，忘了深拷贝输入矩阵。直接修改 graph，会让调用方看到被破坏的输入，排错时非常难发现。拷贝一行代码，值得。

第二，循环顺序写错，k 没有放在最外层。这是正确性错误，不是风格错误。写成 i-k-j 或 i-j-k 都会在负权图上给出错误答案。

第三，对角线没有初始化为 0。后果是「绕道自己」的候选全部失效，距离偏大。

第四，用有限大数当无穷大，且没有在加法前判等。负权边会把这个大数「更新」成假路径，结果看起来有数字，实际全错。

第五，更新 next 时直接写 k。当 i 到 k 的路径还有中间节点时，这样会丢失第一段路径，还原出来的是「跳着走」的假路径。

第六，在每轮中间检查负环。负环的影响可能要到很后面的轮次才传到对角线，提前检查会漏报。正确做法是全部循环结束后再扫对角线。

第七，用 dist[k][j] 判断不可达时写成了 dist[i][j]。这类下标笔误在代码 review 时几乎看不出来，最好的防御是拿一个带负权的小图，手工推几轮结果对拍。

把这些错误清单贴在代码旁边，写完对照一遍，比盲目试错高效得多。

5.8 复杂度推导与常数优化

Floyd-Warshall 的时间复杂度推导非常直接：外层 k 循环执行 V 次，中层 i 循环执行 V 次，内层 j 循环执行 V 次，循环体是常数时间的加减和比较，所以总操作数是 V 的三次方量级，写作 O(V 的三次方)。这个复杂度与边数 E 完全无关，是它最重要的身份标签。

空间复杂度也容易算：核心矩阵是 V 乘 V，O(V 的平方)；加上 next 矩阵仍然是 O(V 的平方)。对比 Bellman-Ford 的 O(V) 附加空间，Floyd 在空间上要奢侈一些，但换来的是全源答案。

常数方面有几个实用的优化手段。第一，中间循环里跳过 dist[i][k] 为无穷的行，能避免大量无意义加法；在最坏情况下这个剪枝不改变复杂度，但实际稀疏图里收益明显。第二，内层循环可以跳过 j 等于 k 的格子，因为 dist[i][k] 加 dist[k][k] 不会比 dist[i][k] 小；同理可以跳过 i 等于 k 的行，不过代码会变丑，收益有限。第三，如果图是无向图，距离矩阵保持对称，可以只更新上三角再镜像复制，常数大约减半；代价是代码复杂度和出错概率上升，工程上通常不值得。

还有一个容易被忽视的缓存因素：内层 j 循环连续访问同一行 dist[i] 的不同列，在行优先存储的语言里是缓存友好的；相反，如果代码把 i 和 j 调换，访问会变成跳列，缓存命中率下降。JavaScript 引擎和大多数语言的二维数组都是行优先，所以保持「k 外层、i 中层、j 内层」不仅是正确性要求，也顺带踩在了性能友好的布局上。

最后给一个规模感受：V 等于 100 时，一百万个更新，毫秒级完成；V 等于 500 时，一亿两千万次更新，大概一秒量级；V 等于 1000 时，十亿次更新，数秒到十几秒。这就是为什么「V 小于等于 500」经常被当作 Floyd-Warshall 的安全线。

六、负环检测：对角线上的警铃

6.1 负环会让最短路失去意义

在讲检测之前，先明确为什么负环是必须被抓住的敌人。所谓负环，就是一条起点和终点相同的环，环上所有边的权重之和是负数。如果图里存在负环，从环上任意一点出发，可以绕着环走一圈，总长度变短；再走一圈，又变短；走无限圈，长度趋近负无穷。于是「最短路径」根本不存在，任何有限长度的答案都没有意义。

flowchart LR
    A["0"] -->|"1"| B["1"]
    B -->|"-5"| C["2"]
    C -->|"2"| A

上面这张三节点图里，0 → 1 → 2 → 0 的环总权重是 1 加负 5 加 2，等于负 2，是一个负环。从 0 出发回到 0，走一圈变负 2，走两圈变负 4，根本没有下界。

Floyd-Warshall 在这样的图上会怎么表现？每一轮更新都可能让某些距离变得更小，而且随着 k 轮推进，负环的影响会沿着可达性传播开。算法跑完后，dist 矩阵里的值不仅不是最短路，甚至可能因为反复绕环而变得荒谬地小。

6.2 检测原理：看对角线

好消息是，负环会在一个特别显眼的地方留下痕迹：矩阵的对角线。

回忆一下初始矩阵：dist[i][i] = 0，因为从 i 到 i 的空路径长度是 0。在无负环的图里，任何从 i 出发又回到 i 的闭合路径都是一个环；如果环的权重是正数，它不可能比 0 短；如果环的权重是 0，它和空路径打平；总之 dist[i][i] 始终等于 0，不会变成负数。

但如果图里存在负环，事情就不一样了。设负环经过节点 u，那么从 u 出发，沿着负环绕一圈回到 u，总长度是负数。Floyd-Warshall 在放行过程中迟早会发现这条绕行路线比 0 更短，于是把 dist[u][u] 更新成负数。更糟的是，这个负值还会向其他节点传播：如果 v 能到达负环、负环又能到达 w，那么 v 到 w 的「距离」也会被拉到负无穷。

所以检测规则只有一句话：算法运行完毕后，检查所有 dist[i][i]，只要存在任何一个小于 0 的值，就说明图中存在负环。

flowchart TD
    A["运行完整的 Floyd-Warshall 三重循环"] --> B["检查所有对角线 dist[i][i]"]
    B --> C["存在某个 dist[i][i] 小于 0？"]
    C -->|"是"| D["图中存在负环，距离结果无意义"]
    C -->|"否"| E["无负环，dist 就是真正的全源最短路"]

用上面那个三节点负环图验证：0 → 1 → 2 → 0 总权负 2。运行完 Floyd-Warshall，dist[0][0] 会变成负 2，dist[1][1] 也会变成负 2（从 1 出发绕一圈：1 → 2 → 0 → 1），dist[2][2] 同样是负 2。三个对角线全是负数，警报拉响。

一个常见的疑问：如果负环只存在于图的一个角落，而某个节点根本到不了负环，它的对角线会不会被误报？不会。dist[i][i] 小于 0 的充分必要条件是「从 i 出发能绕一个负环回到 i」。到不了负环的节点，对角线保持 0，不会被污染；但算法报告「存在负环」时，你应该知道整张图的结果都不可信，因为那些到得了负环的点对已经全部失真。

6.3 与 Bellman-Ford 的负环检测对比

Bellman-Ford 在第 10 篇已经展示过一种负环检测：单源场景下，先做 V-1 轮松弛，再尝试第 V 轮；如果第 V 轮还能让某条边松弛，就说明存在负环。原理是「无负环时，从源点出发的最短路径最多有 V-1 条边；能松弛 V 轮，说明路径边数可以无限增长，只能是负环在起作用」。

Floyd-Warshall 的检测则简单粗暴：不需要额外轮数，直接在结果矩阵上检查对角线。两者的适用场景不同：

Bellman-Ford 是单源算法，适合「只关心一个源点」的负环检测；它还能沿着前驱链把负环上的节点找出来，定位更精确。

Floyd-Warshall 是全源算法，跑完所有点对最短路的同时顺手完成检测，适合「本来就要全源结果」的场景；它只能报告「有或没有」，不容易直接定位负环上的具体节点。

复杂度上，Bellman-Ford 单源是 O(VE)，Floyd-Warshall 是 O(V 的三次方)。如果只想检测一个图有没有负环，而且图很稀疏，用 Bellman-Ford 或 SPFA 的入队次数检测通常更划算；如果图本来就是稠密小图，Floyd 对角线检查是最省事的。

6.4 检测到负环之后怎么办

工程实践中，检测到负环后通常分几步处理：第一步，明确告诉调用方「输入图不合法，最短路无定义」，而不是返回一个看似正常的矩阵；第二步，根据业务决定是修复数据（比如把补贴上限改成非负）还是改用别的度量；第三步，在测试环境用负环用例专门验证检测逻辑，防止上线后静默出错。

还有一个小细节：检测负环要在 Floyd-Warshall 完整跑完之后做，不能在某一轮中间提前退出。因为负环的影响可能要到很晚的轮次才传播到某些对角线；提前退出可能漏报。反正完整运行就是 O(V 的三次方)，多一次对角线扫描只是 O(V)，成本可以忽略。

6.5 负环影响是怎么一步一步扩散的

我们用前面那个三节点三角图，把负环影响扩散的过程走一遍，你就能直观看到「对角线变负」不是魔法，而是一轮一轮松弛出来的。

图的结构再写一遍：0 → 1 权重 1，1 → 2 权重负 5，2 → 0 权重 2。初始矩阵里，对角线全是 0，其余格子只有直接边有值。

第 0 轮放行节点 0，值得关注的变化是 2 → 1：原来不可达，现在可以走 2 → 0 → 1，权重 2 加 1 等于 3。第 1 轮放行节点 1，事情开始不对劲了：2 → 1 已经是 3，而 1 → 2 是负 5，于是从 2 出发绕到 1 再回到 2 的候选是 3 加负 5，等于负 2。这个值比对角线上的 0 小，dist[2][2] 被更新成负 2。负环第一次在矩阵里留下了记号。

第 2 轮放行节点 2，负值开始到处扩散。0 到 1 的候选是 0 → 2 → 1，而 dist[2][1] 现在已经被负环影响，组合出的路径一路走负环，长度不断刷新；1 到 1 的候选也把两条负路径拼在一起，对角线越变越小。等到算法跑完，三个对角线全部是负数。

这里有一个非常值得注意的现象：一旦负环出现，具体更新成什么值会依赖循环里 i、j 的先后顺序，不同实现可能给出不同的「负无穷方向」的数字。这再次说明，有负环时矩阵里的数值没有任何语义，唯一可靠的信息就是「对角线为负，图不合法」。

6.6 为什么有负环时路径还原也不能用

有人可能会想：负环只影响一部分点对，其他点对的距离矩阵是不是还能用？答案是否定的。

原因在于可达性的传递。设负环在节点 u 附近，而节点 v 能走到 u，u 又能走到 w。那么从 v 到 w 的路径可以先走到 u，绕着负环转任意多圈，再去 w。圈数越多，总权重越小，所以 v 到 w 没有最小值；即使某一次算法运行恰好记录了一个有限值，那也只是「恰好跑到的某条路径」的长度，不是最短距离。

更麻烦的是，负环的影响还可能通过路径还原「污染」next 矩阵：next 记录的是最后一次让距离变短的路径，而这条路径里可能包含负环。用这样的 next 还原路径，可能得到一条带着循环的、可以无限转圈的路线。导航软件如果拿着这种路径给用户指路，后果可想而知。

所以工程上的正确姿势是：跑完 Floyd-Warshall 后先检查对角线，一旦发现负环，整张 dist 和 next 全部作废，向调用方抛出明确的错误，而不是返回「看起来能用」的数据。宁可报错，不可静默出错，这是处理负环的唯一正确态度。

七、传递闭包：把加法换成逻辑与

7.1 从距离到「能不能到」

Floyd-Warshall 的递推框架有一个非常优雅的副产品：把「最短距离」换成「能否到达」，同一套三层循环就变成传递闭包算法。

先明确传递闭包是什么。给定一个有向图，我们想知道任意两个节点之间是否存在一条路径，而不关心路径有多长。这个「存在性」信息可以用一个布尔矩阵 reachable 表示：reachable[i][j] 为 true 表示存在从 i 到 j 的路径。注意路径允许经过任意多个中间节点，所以它不只是邻接矩阵。

传递闭包在数学上对应关系的传递性：如果 i 能到 k，k 能到 j，那么 i 一定能到 j。把这种「一步推理」反复应用，直到没有新的可达关系产生，得到的完整矩阵就是传递闭包。

7.2 布尔版递推

仿照最短路版本的状态定义：r[k][i][j] 表示「只允许使用前 k 个节点作为中间节点时，i 能否到达 j」。初始时，r[0][i][j] 表示 i 到 j 是否有直达边，i 等于 j 时显然是 true（空路径）。

第 k 轮放行节点 k，i 到 j 的可达性只有两种来源：

不经过 k：沿用 r[k-1][i][j]。

经过 k：要求 i 能到 k 且 k 能到 j，也就是 r[k-1][i][k] 并且 r[k-1][k][j]。

所以：

r[k][i][j] = r[k-1][i][j] 或者 ( r[k-1][i][k] 并且 r[k-1][k][j] )

对比最短路递推：

d[k][i][j] = min( d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j] )

发现了吗？两个式子长得一模一样：min 对应「或者」，加法对应「并且」。距离的「绕道 k 是否更短」变成了可达性的「绕道 k 是否可行」。这就是为什么说传递闭包只是 Floyd-Warshall 的一个布尔版本。

flowchart TD
    A["reachable[i][j]"] --> B["不经过 k：reachable[i][j] 本来就为真"]
    A --> C["经过 k：reachable[i][k] 为真且 reachable[k][j] 为真"]
    B --> D["任一成立即可达"]
    C --> D

7.3 代码：只改一个操作

function transitiveClosure(graph: boolean[][]): boolean[][] {
  const n = graph.length;
  const reachable = graph.map((row) => row.slice());

  for (let i = 0; i < n; i++) {
    reachable[i][i] = true;
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (!reachable[i][k]) continue;
      for (let j = 0; j < n; j++) {
        reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j]);
      }
    }
  }

  return reachable;
}

如果把这段代码和最短路版本并排看，差别几乎只有三处：输入从权重矩阵变成布尔矩阵；初始对角线从 0 变成 true；min 加号变成「或」加「与」。核心的 k-i-j 三重循环结构原封不动。这也是「算法框架比单个算法重要」的绝佳例证：同一个递推骨架，换一组运算，解决的是另一个问题。

这里同样要注意 k 在最外层，理由和最短路版本一模一样：第 k 轮用到的 reachable[i][k] 和 reachable[k][j] 在本轮内不会被更新成「从 false 变 true」的新值，因为本轮更新只会尝试把 reachable[i][j] 置为 reachable[i][k] && reachable[k][j]；对于 reachable[i][k] 本身，候选是 reachable[i][k] && reachable[k][k]，而 reachable[k][k] 为 true，所以它不会改变。布尔版本下「绕道自己」永远成立，原地更新自然安全。

7.4 应用场景

传递闭包的应用非常广泛，举几个有代表性的：

依赖管理。软件包的依赖关系是有向图：A 依赖 B 表示 A → B。传递闭包可以回答「安装 A 之后，实际上会带进来哪些包」「删除 B 会影响哪些上层包」。包管理器、构建系统的增量编译都依赖这类可达性查询。

数据库与编译。数据库外键、视图之间的依赖，代码模块之间的 import 关系，都可以建模成有向图。想知道「改这个表会影响哪些视图」「重构这个模块需要重新编译哪些模块」，本质就是在问传递闭包。

权限与信任传播。如果授权关系是「A 信任 B，B 信任 C」，那么 A 是否间接信任 C？布尔可达性直接回答。知识图谱里的「A 是 B 的朋友，B 是 C 的同事，那么 A 和 C 之间有没有某种关系链」也是同一类问题。

课程与任务前置。课程 A 是课程 B 的前置，B 又是 C 的前置，那么 A 就是 C 的间接前置。学生选课系统要检查「先修条件是否满足」，背后就是可达性查询。

flowchart LR
    A["模块 A"] --> B["模块 B"]
    B --> C["模块 C"]
    A -.->|"传递闭包：A 可达 C"| C

上图是依赖可达性的缩影：A 依赖 B，B 依赖 C，虽然 A 和 C 之间没有直接边，但传递闭包告诉我们 A 的修改会波及 C，A 的安装会带来 C。

7.5 复杂度与替代方案

布尔版传递闭包的时间复杂度同样是 O(V 的三次方)。当 V 很大时，可以改用「每个节点做一次 DFS/BFS」：从每个源点出发遍历，标记所有可达节点，总复杂度 O(V(V+E))。稀疏图里这种方法通常更快；稠密小图里，三重循环的简单实现更省心。如果追求极致，还可以用位运算把每行当成一个位向量，用「按位或」一次性更新整行，常数能小很多，但那是优化话题，本篇不展开。

7.6 传递闭包与逐点 BFS 的对比

求传递闭包最朴素的替代方案是：对每个节点做一次 BFS 或 DFS，把从它出发能到达的所有节点标记成 true。总复杂度是 O(V(V+E))。这个方案思路简单、代码也简单，那为什么还要学布尔版 Floyd-Warshall？

关键在于图的形态。当图很稀疏，E 接近 V 时，O(V(V+E)) 大约是 O(V 的平方)，比 O(V 的三次方) 快一个量级，逐点 BFS 明显更优。但当图很稠密，E 接近 V 的平方时，逐点 BFS 变成 O(V 的三次方) 量级，和 Floyd 一样；此时三重循环版本的优势在于：实现短、没有递归栈风险、不需要维护每个源点的访问标记，而且在竞赛和面试里写起来几乎不会错。

还有一个工程细节：BFS 方案天然适用于「只查少数源点」的可达性问题，而传递闭包矩阵适合「高频随机查询」。如果业务里经常问「任意两个节点可达吗」，提前算好矩阵，每次查询是 O(1)；如果只关心少数几个源点，现场 BFS 更划算。这和全源最短路 vs 单源最短路的取舍一模一样，选型逻辑完全相通。

7.7 用强连通分量的视角看传递闭包

传递闭包还有一个更深的数学结构：有向图的强连通分量。一个强连通分量里的任意两个节点互相可达，所以分量内部的可达性矩阵是一整块 true；分量之间则形成一张有向无环图。

利用这个结构，可以先求强连通分量，把图压缩成 DAG，再在 DAG 上求可达性。节点数通常大幅减少，计算和存储都更省。这也是为什么研究传递闭包的人几乎都会研究强连通分量：两者互为表里。图系列前面讲 DFS 时提到过相关概念，后续如果专门写强连通分量，我们可以回头再对比一遍：Floyd 的布尔版是「暴力但通用」的闭包算法，Tarjan 或 Kosaraju 加 DAG 传播是「利用结构」的优化路线。

对初学者来说，先把布尔版 Floyd-Warshall 写熟，理解「可达性也是可递推的量」，就已经为进阶打下了基础。知道存在更强的手段，但不急着现在掌握，是更合理的节奏。

7.8 一个依赖可达性的完整小例子

纸上谈兵不如一个具体例子。假设一个软件仓库里有四个包：A、B、C、D，依赖关系如下：A 依赖 B，B 依赖 C，A 依赖 D，D 也依赖 C。把这个关系画成有向图：A → B，B → C，A → D，D → C。

初始布尔矩阵里，直接依赖是 true，对角线是 true（自己总可以「空路径」到达自己）：

reachable	A	B	C	D
A	true	true	false	true
B	false	true	true	false
C	false	false	true	false
D	false	false	true	true

跑完传递闭包后，唯一的新增关系是 A → C：因为 A 能到 B，B 能到 C，所以 A 间接依赖 C。最终矩阵：

reachable	A	B	C	D
A	true	true	true	true
B	false	true	true	false
C	false	false	true	false
D	false	false	true	true

这张矩阵可以回答两类高频问题。第一类：安装 A 之后，实际会引入哪些包？答案是 A 所在行里所有 true 的节点，也就是 B、C、D。第二类：如果删除 C，哪些包会受影响？答案是 C 所在列里所有 true 的节点，也就是 A、B、D——它们都直接或间接需要 C。

注意一个细节：闭包矩阵的行和列含义不同，读的时候要分清。「i 行是 i 能到谁」，「j 列是谁能到 j」。实际业务里「上游影响」和「下游依赖」经常同时需要，那就把矩阵按行、按列各查一次，都是 O(1)。这也是预计算传递闭包最大的价值：把图上的复杂推理，全部压成矩阵里的常数时间查询。

八、应用场景与算法选型

8.1 什么时候真正需要全源最短路

单源算法足够覆盖很多业务场景：用户输入起点和终点，现场算一次。但有一类场景必须提前算好全源答案。

第一类是高并发查询。地图导航、打车平台每天有海量「起点到终点」的请求，如果每个请求都现场跑 Dijkstra，服务器压力很大。预先把所有点对距离算好，查询退化成查表：O(1) 拿到距离，再配合 next 矩阵还原路径。Floyd-Warshall 正好在「预计算阶段」一次性把表和路径全部备好。

第二类是需要整张表做分析。社交网络研究「任意两人之间平均距离」，物流网络评估「任意两个仓库之间的运输成本」，网络拓扑计算「图的直径」（所有点对距离的最大值）。这些任务要求全源矩阵，而不是单源结果。

第三类是图本身很小但很稠密。节点数几百、边数接近完全图时，Dijkstra 跑 V 次的常数和代码复杂度都不如 Floyd 一把梭。面试和竞赛里，「V 小于等于 300 到 500，要求所有点对最短路」几乎就是明示用 Floyd-Warshall。

第四类是传递闭包类问题。前面说过，只要把「距离」换成「可达性」，同一套代码就变成闭包计算。很多题目表面问「两点之间是否可达」「依赖关系是否传递」，实际都是在考这个布尔版本。

8.2 什么时候不要用 Floyd

Floyd 最大的软肋是 O(V 的三次方) 对节点规模敏感。V 等于 1000 时，十亿次更新在现代机器上大约是几秒到十几秒的量级，还能忍；V 等于 5000 时，一千多亿次更新，直接不可行。

如果图很稀疏（E 远小于 V 的平方）而且节点很多，全源最短路更常用的做法是 Johnson 算法：先跑一次 Bellman-Ford 做重赋权，把负权边消掉，再对每个源点跑一次堆优化 Dijkstra，总复杂度 O(VE + V(E+V)log V)。稀疏图上它明显优于 Floyd。

如果只关心少数几个源点，那就更没必要全源了：直接对那几个源点各跑一次单源算法。所以选型的第一原则永远是「先问清楚问题规模与形态，再挑算法」，而不是无脑上 Floyd。

8.3 选型总结表

需求	推荐算法	时间复杂度	备注
单源、无权图	BFS	O(V+E)	层序遍历天然给出最短步数
单源、非负权	Dijkstra（堆优化）	O((V+E) log V)	最常用的单源算法
单源、允许负权、无负环	Bellman-Ford / SPFA	O(VE) / 期望更快	能顺带检测负环
全源、稠密图或小图	Floyd-Warshall	O(V³)	支持负权，代码最短
全源、稀疏大图	Johnson	O(VE + V(E+V) log V)	重赋权后再跑 V 次 Dijkstra
只问是否可达	传递闭包布尔版	O(V³)	一行改动版 Floyd
只想检测负环	Bellman-Ford 或 Floyd 对角线	O(VE) 或 O(V³)	按规模选择

这张表值得反复看。面试里最常见的追问就是「为什么这里不用 Dijkstra」「有负权怎么办」「全源的话选什么」，答案都在表里。

8.4 一个决策流程

flowchart TD
    A["要算哪些点对的最短路？"] --> B["只要一个源点"]
    A --> C["要所有点对"]
    B --> D["边权非负？"]
    B --> E["有负权？"]
    D --> F["Dijkstra"]
    E --> G["Bellman-Ford 或 SPFA"]
    C --> H["图是否稠密或节点较少？"]
    H -->|"是"| I["Floyd-Warshall"]
    H -->|"否，图很大且稀疏"| J["Johnson"]
    C --> K["只关心能否到达？"]
    K --> L["传递闭包布尔版"]

8.5 工程实现的小建议

把 Floyd-Warshall 封装成独立函数时，有几个工程细节值得养成习惯。

输入校验：先检查 n 是否为零，空图直接返回空矩阵；检查对角线初始值是否为 0，如果调用方给了非零对角线，结果会错。

结果约定：函数返回的 dist 矩阵应该注明「未检测负环，调用方自行检查对角线」还是「内部已经检测并抛出异常」。两种风格都可以，但要写清楚，避免下游把失真数据当真。

数值安全：如第五节所说，统一用 Infinity 表示不可达，别混用大常数；如果图里有权重很大的边，加法可能溢出，必要时用 BigInt 或加判断。

路径还原的配套：如果业务需要具体路径，记得同时维护 next 矩阵，并在文档里写清楚 next 的含义。很多线上 bug 都来自「知道最短距离，却不知道最短路径」的尴尬。

8.6 与其他图算法思想的联系

Floyd-Warshall 的动态规划思想其实无处不在。它和第 10 篇 Bellman-Ford 的「松弛」本质上是同一个动作：不断尝试用「绕路」改进当前答案。Bellman-Ford 按边数轮次松弛，Floyd 按中间点集合轮次松弛；一个用邻接表，一个用邻接矩阵。理解这一点后，你会发现最短路家族是一棵大树，Floyd 只是其中一根特别粗壮的枝条。

下一篇我们要离开最短路，进入最小生成树的领地。那里的问题不再是「怎么走最短」，而是「怎么连通最便宜」，算法主角从动态规划换成贪心与并查集。先记住这个转折：最短路关心路径长度，最小生成树关心连通成本，两者是图论里最容易混淆、也最值得对比的两个经典问题。

8.7 全源矩阵的衍生产物：直径与中心

全源距离矩阵算出来之后，很多图论指标可以顺手获得，其中最有名的是图的直径和中心。

图的直径是「所有可达点对之间最短距离的最大值」。直观理解：网络里最远的两个节点隔了多远。计算方式很简单：扫描整个 dist 矩阵，在有限值里取最大值。直径用于衡量网络的传播延迟上界：消息从任意节点发出，最多经过「直径」这么远就能到达所有能到的节点。社交网络研究里的「六度分隔」和「网络半径」，物流网络评估「最远配送距离」，都用得上这个指标。

中心节点则是「到所有节点最大距离最小的节点」。对每个节点 i，先算它到所有可达节点的最大距离，再在所有节点里挑最大值最小的那个。中心节点适合做服务器选址、仓库选址：把服务器放在中心，能保证最坏情况下的访问延迟最低。这个「最小化最大值」的思路叫极小化最大准则，在运筹学里非常常见。

这两种指标都建立在全源矩阵之上，这也解释了为什么有些业务明明只关心一两个数字，却仍然要先跑 Floyd-Warshall：因为「直径」和「中心」本身就要求知道所有点对的距离，单源算法帮不上忙。

8.8 竞赛与面试里的 Floyd 出场姿势

最后总结一下 Floyd-Warshall 在各种场合最常见的出场方式，帮你建立「看到什么条件，想到什么算法」的反射。

条件一：题目要求所有点对最短路，且 V 在几百以内。直接写三重循环，不要犹豫。就算图是稀疏的，V 小的时候 Floyd 的代码量和调试成本依然最低。

条件二：图里有负权边，但题目保证无负环，又要全源答案。Dijkstra 失效，Bellman-Ford 跑 V 次太慢，Floyd 是标准答案。

条件三：题目问「两点之间是否可达」「依赖是否传递」「需要 O(1) 回答任意可达性」。把 min 和加法换成或与与，写布尔版。

条件四：题目问最小环。Floyd-Warshall 有一个经典技巧：在第 k 轮更新 dist 之前，利用当前矩阵和节点 k 的出入边尝试闭合环，从而在 O(V 的三次方) 内找到最小环。这个变体稍微复杂一点，但很多竞赛题会包装成「旅行团最少几个人能回到起点」之类的形式。

条件五：题目说「任意两点之间最少换乘几次」。换乘次数不关心路程长短，本质是无权图的最短路，BFS 跑全源或者布尔闭包都能做；但如果图有密度优势，Floyd 版本也能直接改。

面试官还喜欢追问三连：为什么 Dijkstra 不能处理负权？为什么 Floyd 支持负权？负环怎么处理？这三问分别对应图系列第 9 篇、本篇第二三节和第六节。能把这三个问题用自己的话讲清楚，Floyd-Warshall 这一关基本就过了。

8.9 稀疏大图上的全源答案：Johnson 算法

选型表里提到了 Johnson 算法，这里稍微展开讲一下它和 Floyd 的分工，方便你在真实项目里做决定。

Johnson 算法的思路分三步。第一步，加一个虚拟源点，向所有节点连权重为 0 的边，跑一次 Bellman-Ford，算出每个节点的一个「势能」h(v)。第二步，用势能对每条边重赋权：新权重 w’(u, v) 等于 w(u, v) 加 h(u) 减 h(v)。可以证明，在无负环的图里，所有新权重都是非负的，而且任意两点之间的最短路径集合不会因为重赋权而改变，只是每条路径的总长都统一平移了 h(源点) 减 h(终点)。第三步，对每个源点跑一次堆优化 Dijkstra，再用势能把距离还原成真实值。

Johnson 的总复杂度是 O(VE + V(E+V) log V)。对比 Floyd 的 O(V 的三次方)：当图稀疏，E 接近 V 时，Johnson 大约是 O(V 的平方 log V)，明显更快；当图稠密，E 接近 V 的平方时，Johnson 退化成 O(V 的三次方 log V)，比 Floyd 慢，而且实现复杂得多。

所以选型的直觉可以概括成两句话：小图、稠密图、想要代码短、想顺手拿传递闭包，选 Floyd；大图、稀疏图、追求性能、不介意实现复杂度，选 Johnson。大多数面试场景里，题目给出 V 不超过几百，就是默认你写 Floyd。

还有一类特殊情况值得一提：如果图是无负权的稀疏大图，也可以直接跑 V 次 Dijkstra，跳过 Johnson 的重赋权步骤，代码简单得多。此时复杂度是 O(V(E+V) log V)，稀疏图上和 Johnson 几乎一样快。总之，算法选型没有银弹，先看负权、再看密度、再看规模，一步步排除，答案自然浮现。

九、Floyd 要点速查表

算法进入收尾阶段，我们把整篇的干货浓缩成一张速查表。复习的时候只看这一节就够了；如果哪一行看不明白，再回正文对应小节。

项目	内容
解决的问题	所有点对最短路，允许负权边，不允许负环
状态定义	d[k][i][j]：只允许前 k 个节点作为中间点时，i 到 j 的最短距离
初始矩阵	dist[i][j] = 边权；无边为 ∞；对角线为 0
递推式	d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])
循环顺序	k 在最外层，i、j 在内层，i、j 顺序无所谓
原地更新依据	第 k 轮里 dist[i][k] 与 dist[k][j] 不会变小（dist[k][k] ≥ 0）
时间复杂度	O(V³)
空间复杂度	O(V²)，路径还原再加 O(V²) 的 next 矩阵
负环检测	跑完后检查 dist[i][i] < 0 是否成立
路径还原	next[i][j] 记录 i 到 j 最短路径的下一跳，更新时 next[i][j] = next[i][k]
传递闭包	把 min 换成或、把加换成与，布尔矩阵直接复用三层循环
适用场景	稠密图、小图、预计算查询表、传递闭包、依赖可达性
不适用场景	节点数很大的稀疏图（改用 Johnson），单源问题（直接用单源算法）

除了表格，还有三个「一句话」值得贴在墙上：

第一，Floyd-Warshall 是给节点发通行证的算法，第 k 轮就是「节点 k 正式成为中转站」的轮次。

第二，k 在最外层不是风格问题，是正确性问题；写错循环顺序，带负权的图上一定翻车。

第三，同一个递推骨架，用 min 加加号是最短路，用或加与是传递闭包。掌握骨架，就同时掌握了两把武器。

最后再强调一次复杂度直觉：O(V 的三次方) 意味着节点数翻倍，时间变八倍。所以看到 V 等于 10000 的图，第一反应应该是「全源最短路需要换思路」，而不是硬上 Floyd。

9.1 三个容易混淆的概念辨析

学完 Floyd-Warshall，最常被搞混的是三组概念，这里一次性理清。

第一组：最短路与传递闭包。最短路回答「从 i 到 j 最短有多远」，输出数值；传递闭包回答「从 i 到 j 能不能到」，输出布尔值。两者共用同一个递推骨架，但语义完全不同：一个在实数域上取最小值，一个在布尔域上取「或」和「与」。写代码时如果你只改了数据类型、忘了改运算符，结果一定错得莫名其妙。反过来说，只要你记住了递推骨架，两套代码都能默写出来。

第二组：负权边与负环。负权边只是权重小于零的单条边，只要图中不存在「总权重为负的环」，最短路依然良定义，Floyd 可以正常处理；负环是一整圈闭合路径的权重和为负，它会让最短路失去下界，任何结果都没有意义。一句话记忆：负权边是允许的客人，负环是必须报警的强盗。Dijkstra 连负权边都怕，Floyd 只怕负环，Bellman-Ford 则能在单源场景下把负环抓出来。

第三组：单源与全源。单源问题只问一个起点，全源问题问所有起点。很多同学看到「任意两点」就直接上 Floyd，但如果查询次数很少，对每个查询单独跑一次 Dijkstra 反而更快；看到「所有点对」也别急着 Floyd，先看 V 的规模和图是否稀疏，Johnson 和逐点 BFS 可能更合适。选型不是背结论，而是先量化问题。

顺便讲一个算法命名的小知识：这个算法的两个名字来自两位作者。Warshall 在 1962 年提出了布尔矩阵的传递闭包算法，Floyd 在同一年独立提出了带权最短路版本，后人把两人的工作合称为 Floyd-Warshall。所以「Floyd-Warshall 能算传递闭包」并不是巧合，它本来就是这个算法家族的原点之一。理解这段历史，有助于把最短路版本和布尔版本当成同一个思想的两种形态，而不是两个孤立算法。

十、自测题：七道题检验掌握程度

十一、下一篇预告：最小生成树

图系列第 12 篇将告别最短路，进入图论另一个经典分支：最小生成树。我们会回答一个全新问题：给定一张连通的无向带权图，怎样选出若干条边，让所有节点连通，同时总权重最小？

这篇的主角是 Kruskal 算法和 Prim 算法。Kruskal 把所有边按权重排序，用并查集从小到大选边；Prim 从任意节点出发，像 Dijkstra 一样用优先队列扩张连通区域。我们会讲到它们背后的统一原理——切分定理，也会把「最短路」和「最小生成树」这对最容易混淆的兄弟彻底掰开：前者让两个点的路径最短，后者让整个图连通的代价最小；负权边对最短路影响巨大，对最小生成树却完全无所谓。

第 12 篇里，我们会用真实的电网、光纤和城市供水案例展示最小生成树的用武之地，并给出完整的代码、手算过程和复杂度分析。到那时候，图系列最核心的「四大算法家族」——遍历、最短路、最小生成树、拓扑与连通性——就基本集齐了。我们下一篇见。