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] | 只允许直接边 |
| 允许中间点 1 | 0→2 改为 3+(−1)=2 | 经 1 更短 |
| 其余轮 | 无进一步改进 | 有向不可达位置仍为 ∞ |
窄屏可左右滑动表格,阅读完整计算与理由。
最终 0 到 2 的最短距离是 2,2 到 0 仍不可达。
04为什么这个方法成立
- k=0 的基础矩阵表示不含内部节点的路径。
- 按是否经过新节点 k 分类,不漏且覆盖所有最优可能。
- 逐步允许全部节点后得到完整最短路径;对角线负值暴露负环。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
为什么 i 到自己初始为 0?
需要一点提示
可以不走任何边。
查看解析与答案
空路径成本为 0;若之后变负,说明存在负成本闭游走。
负边一定导致 None 吗?
需要一点提示
负边与负环区别。
查看解析与答案
不一定,本例有负边但无环,结果有效。
要恢复 0→2 的具体路径怎么办?
需要一点提示
更新时还应记录决策。
查看解析与答案
维护 next 或中间点矩阵,改进时记录第一步或分割点,再沿记录重建,另处理不可达与负环。