2.3 Floyd-Warshall与Johnson：全源最短路径

2.3 Floyd-Warshall 与 Johnson：全源最短路径

本节摘要：全源最短路径（APSP）要求图中任意两顶点间的最短距离。Floyd-Warshall 用一个三重循环的动态规划，以点数立方的时间一次性算出整个距离矩阵，代码仅五行，是小规模稠密图的绝对主力；Johnson 算法（1977 年提出）先用 Bellman-Ford 给顶点重赋权、把负权边转成非负，再对每个源点各跑一次 Dijkstra，总复杂度更适合大稀疏图。本节讲透两者的原理、实现边界与选型。

本节地图

阅读完本节，你应当能够：

1. 写出 Floyd-Warshall 的状态转移并解释"中转点"的含义；
2. 说明循环层次（中转点必须放最外层）为什么不可交换；
3. 用距离矩阵对角线检测负环；
4. 描述 Johnson 的重赋权公式并证明其非负性与保序性；
5. 按图规模与稠密度在两者间选型。

一、问题与直觉：为什么要"全源"

单源算法回答"从 A 出发到每个点多远"。但有些业务天然要问"任意两两之间多远"：城市交通规划要预生成全量 OD 矩阵（起点—终点矩阵）供查询；社交平台计算任意两用户的"关系距离"；金融风控扫描全部交易对之间的套利环路。对这类需求，朴素做法是"每个点各跑一次 Dijkstra"，未必错，但不一定最优——最优解取决于图的形态，这正是本节两条路线的分岔口。

二、Floyd-Warshall：五行的动态规划

状态设计：dist 为距离矩阵，dist 表示当前"允许经过前 k 个顶点中转"时 i 到 j 的最短距离。

转移方程：第 k 轮，i 到 j 的最短路要么不经过 k（保持原值），要么经过 k（拆成 i 到 k 加 k 到 j 两段）：

第k轮：dist为 min 原 dist 与 dist加 dist 的较小者
​

为什么中转点必须在最外层：dist 的定义绑定了"前 k 个点"这个阶段，k 是动态规划的阶段变量，必须最先循环。把 k 放到内层会提前使用"未经完整阶段"的表项，结果不可靠。这是该算法最经典的实现错误。

def floyd_warshall(n, weight):
    # weight 为 n 乘 n 矩阵 无边处用无穷大 对角线为0
    dist = [row[:] for row in weight]
    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]
    return dist
​

性质清单：时间与空间都是点数立方级（空间存距离矩阵）；允许负权边；若迭代结束后某对角线 dist 变为负数，说明存在负环——绕这个环一圈总长为负，回到自身反而更"近"。Floyd-Warshall 由 Robert Floyd 与 Stephen Warshall 分别独立提出（前者给出最短路形式，后者给出传递闭包形式），名字里带着这段历史。

执行直觉：算法共 n 轮，第 k 轮做完后，所有"只允许拿前 k 个点当中转站"的最短路都已就位。可以把它想象成逐个开放新的中转机场：每开一个，全网络的两两距离表就整体刷新一次，n 轮后所有机场全部开放，表格收敛为最终答案。

三、Johnson：重赋权 + Dijkstra 的组合拳

大稀疏图上，点数立方的 Floyd-Warshall 不可承受（100 万顶点意味着 10 的 18 次方级操作）。Johnson 的方案分三步：

1. 加虚拟源点：新建顶点 s，从 s 到每个原顶点连一条权重为 0 的边，跑一遍 Bellman-Ford 求出 s 到各点的最短距离 h。若检出负环，直接终止（原图无解）。
2. 重赋权：对每条边改为"原权重加起点 h 减终点 h"。可以证明：新权重全部非负（h 的三角不等式保证），且任意一条路径的总权重恰好增加"起点 h 减终点 h"——首尾相消，中间项全部抵消。因此新旧图的最短路路径本身完全一致，只是账面数值平移。
3. 逐点 Dijkstra：对每个顶点各跑一次非负权的 Dijkstra，最后把结果减去"起点 h 减终点 h"还原为真实距离。

新权重表示：w加上h起减h终
路径总权重增量 = h起 − h终 （与中间经过哪些点无关）
​

总复杂度为"点数乘以 Dijkstra 单次开销"，用二叉堆即约为"点数乘以边数乘以 log 点数"，再加一次 Bellman-Ford。对稀疏图，这远优于点数立方。代价是实现链路长：三步、两种算法协作、最后还要还原——原始文集也直言它"算法实现较为复杂"。

两条路线对比

全源算法路线分岔

⚠️ 常见坑：Floyd-Warshall 的三重循环把 k 写进内层。代码照样能跑、不报错，小样例甚至常常结果正确，规模一大就悄悄出错——属于典型的"潜伏型"实现 bug。另一个坑：初始化矩阵时忘了"无边处用大数、对角线为 0"，会把不连通和零距离混为一谈。

💡 关键直觉：Johnson 的重赋权像给每个城市发一张"海拔补偿券"——每条路的账面价加上起点海拔减去终点海拔，环路自动抵消，所有价格变成非负，而"哪条路最便宜"的排名原封不动。Dijkstra 只需要"价格非负"，不在乎价格被平移过。

四、深入一层：Floyd 的三重小循环与传递闭包

Floyd-Warshall 有一个常被忽视的"隐藏产出"：把更新条件从"距离更短"改成"存在通路"，它就变成传递闭包的计算——回答"任意两点之间是否存在路径"。这正是 Warshall 当年独立提出的原始形式，Floyd 把它推广到了最短路。这个视角很有用：可达性矩阵、最短路矩阵、甚至"任意两点间最小容量瓶颈"（把 min 与加法换成 min 与 min），都能套同一个三重循环骨架——动态规划的结构不变，代数系统可换。这类"半环上的 Floyd"思想在数据库传递查询、正则可达性里都有身影。

Johnson 的重赋权则引出另一个漂亮概念：h 本质上是图的一个"势函数"（potential）。重赋权公式"边权加 h 起减 h 终"在物理上恰似电势差——路径的"势差"只取决于两端，与走法无关。凡满足这个性质的变换都不改变最短路的路径选择，只平移账面数值。理解了势函数，你就为将来学习费用流（负权最短路的常态化需求）备好了关键工具。

常见疑问解答

Floyd 能求"具体路径"而不只是距离吗？

能，配一个"后继矩阵"或"中转点矩阵"即可：松弛成功时记录"i 到 j 当前经哪个中转点 k"，输出路径时递归展开。注意矩阵要随更新同步维护，忘了同步是最常见的实现错误之一。

Johnson 的虚拟源点为什么连的是零权边？

零权保证 h 的计算"不偏袒"任何顶点——h 就是从虚拟点出发的真实最短距离。若连正权边，h 会被整体抬高一个不均匀的量，重赋权的非负性保证反而可能被破坏。虚拟点在完成使命后即可弃用，它不进入任何最终答案。

两者都能处理负权，那负环呢？

都能检测但语义略不同：Floyd 看"对角线是否变负"（图中任何位置的负环都能暴露）；Johnson 在 Bellman-Ford 阶段只能暴露"可达虚拟点"的负环——由于虚拟点连向所有点，原图全部负环都可达，所以两者在此等价。检测到负环时都应终止并上报，而不是继续计算。

点数在"几百到几千"之间，到底选谁？

经验分界：点数千级以下、且需要频繁做"任意点对"查询，Floyd 的一次性立方投入最划算（算完查表是 O(1)）；点数上万或只需稀疏的查询，Johnson 或"按需跑 Dijkstra"更合适。还有一个折中：缓存频繁的 Dijkstra 结果，把全源问题化解成热点单源问题——业务查询往往高度集中在少数源点。

动手实验：给 Floyd 做一次"层序透视"

Floyd 的 k 循环常被当成黑盒，值得做一次透视实验：取一个 6 顶点的图，每个 k 轮结束后打印整张距离矩阵。你会看到矩阵逐轮"塌缩"——前几轮还满是无穷大，中段数值此起彼伏地被中转路径刷新，最后一轮趋于平静。把每一轮的矩阵纵向排开，"开放中转机场"的比喻就成了看得见的画面。再做一次错误示范：把 k 挪到最内层跑同一个图，对比结果差异——多数小图恰好不错，找一个会错的例子（比如带特定中转依赖的图），你会对"阶段变量必须最外层"有刻骨的记性。

全源结果的缓存策略

全源结果通常是"预计算一次、查询无数次"的形态，缓存设计有三个要点：按需计算——只对查询过或高频的源点跑 Dijkstra，冷数据不预付；版本失效——边权更新后标记脏区间，只重算受影响的源点；分层存储——热门点对的结果放内存缓存，全量矩阵落盘按需加载。这三招让"全源"从一次性大计算变成可持续服务的资产。

Floyd 的三重循环能并行或向量化吗？

很能，这也是它老而弥坚的原因之一：k 固定时，内层"对全部点对做一次最小值更新"是纯粹的矩阵运算，天然适合按行并行与 SIMD 向量化，多数数值库能把 Floyd 推到接近硬件极限。点数三百左右的距离矩阵，优化良好的实现毫秒级完成——"复杂度丑但常数极美"，是 Floyd 在中小规模场景持续流行的真实原因。

补充一个历史细节：Floyd 的这篇工作发表于一九六二年，Warshall 的传递闭包版本更早一年，两者共享的三重循环骨架是动态规划史上被引用最多的代码片段之一；Johnson 算法则一九七七年问世，专为稀疏图的全源需求而生。

一句话总结：小而密找 Floyd，大而疏找 Johnson——全源问题没有银弹，只有形态匹配。

要点串联

• 问题定位：APSP 求任意两两最短距离，典型需求是 OD 矩阵、关系距离、套利扫描。
• Floyd 状态设计：dist 表示允许经过前 k 个点中转的最短距离，中转点必须放最外层。
• Floyd 性能：点数立方时间与平方空间，五行核心，稠密小图首选；对角线为负即有负环。
• Johnson 三步：虚拟源点跑 Bellman-Ford 求势函数 h；边权加 h 起减 h 终完成非负化；逐点 Dijkstra 后还原。
• 重赋权本质：任意路径总权重只平移"h 起减 h 终"，最短路的路径选择不变。
• 选型结论：点数百级内用 Floyd，万级以上稀疏图用 Johnson；非负权大图也可退化为"逐点 Dijkstra"。
• 历史注脚：Floyd 与 Warshall 独立提出同一框架；Johnson 算法发表于 1977 年。

通用图的工具箱到这里齐了。下一节看两类"结构特殊"的图——DAG 与无权图，它们的额外结构允许我们把最短路算得更快、更简单。