专题进阶 · 图算法推荐总顺序 · 第 58 / 148 课

用允许的中间节点集合定义状态,解释为什么 k 必须放在最外层。

先学会这些,再进入本课 DP 思想 图的表示
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

Floyd–WarshallFloyd–Warshall

依次允许每个中间点,更新所有点对距离,时间 O(V³)。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用允许的中间节点集合定义状态,解释为什么 k 必须放在最外层。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

小规模稠密有向图,需要回答任意两点之间的最短距离,怎样一次求出所有点对?

02一步步得到方法

不是随意写三个循环

定义 D_k[i][j] 为路径内部只允许使用前 k 个节点时的最短距离。新增允许节点 k 后,最优路径要么不经过 k,要么分成 i→k 与 k→j 两段,因此取两者最小值。

在没有负环的前提下,这个状态可原地更新。必须让 k 在最外层,保证某轮围绕同一个允许中间点集合推进;把循环随意换成 i,j,k 不再表示同一个递推。

初始化承载图的语义

dist[i][i]=0 表示空路径;直接边写入权重,多重边取最小;没有边设为正无穷。可以处理负边,但负环会使部分最短路不存在;结束后若 dist[v][v]<0,就检测到负环。

本课有负环时统一返回 None。更精细实现可标记所有能到达负环且从负环可到达的点对为负无穷,但不要把普通距离矩阵误当作这种完整分类。

最外层 k 决定允许的中转集合

处理 k 之前,距离只允许使用编号较小的点作中转。处理 k 时,路径要么不经过 k,要么分成 i→k 和 k→j 两段,所以取 min(dist[i][j],dist[i][k]+dist[k][j])。

k 放在最外层正是为了维持这个状态含义。随意换成 i 或 j 最外层,单遍原地更新一般不再对应相同递推,不能靠公式看起来相同就认为等价。

03把一个小例子完全算清楚

边 0→1:3,1→2:−1,0→2:9。

步骤计算与状态为什么这样做
初始行 0[0,3,9]只允许直接边
允许中间点 10→2 改为 3+(−1)=2经 1 更短
其余轮无进一步改进有向不可达位置仍为 ∞

窄屏可左右滑动表格,阅读完整计算与理由。

最终 0 到 2 的最短距离是 2,2 到 0 仍不可达。

04为什么这个方法成立

  1. k=0 的基础矩阵表示不含内部节点的路径。
  2. 按是否经过新节点 k 分类,不漏且覆盖所有最优可能。
  3. 逐步允许全部节点后得到完整最短路径;对角线负值暴露负环。

05把推导翻译成代码

Python · 可独立运行的教学实现

def floyd_warshall(n, edges):
    d = [[float("inf")]*n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u,v,w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return None if any(d[i][i] < 0 for i in range(n)) else d

逐个理解关键决定

for k in range(n)
外层代表状态阶段,不只是性能上的循环排列。
min(d[u][v], w)
平行边只保留最小直接成本,不能让较差后出现边覆盖。

06时间、空间与实现范围

时间 O(V³),空间 O(V²),适合点数较小的全源问题。

若图很大且稀疏,重复单源搜索可能更合适;矩阵存储本身也可能成为瓶颈。

07改变条件,检查哪里会出错

把没有边初始化为 0

会凭空加入零成本路径;只有对角线空路径为 0。

存在负环仍把所有数值解释为有限最短路

对角线变负可揭示负环,但还需判断哪些起终点可通过该环相连,才能标记受影响的路径。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

为什么 i 到自己初始为 0?

需要一点提示

可以不走任何边。

查看解析与答案

空路径成本为 0;若之后变负,说明存在负成本闭游走。

练习 2 · 边界与辨析

负边一定导致 None 吗?

需要一点提示

负边与负环区别。

查看解析与答案

不一定,本例有负边但无环,结果有效。

练习 3 · 变式与迁移

要恢复 0→2 的具体路径怎么办?

需要一点提示

更新时还应记录决策。

查看解析与答案

维护 next 或中间点矩阵,改进时记录第一步或分割点,再沿记录重建,另处理不可达与负环。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。