Floyd–Warshall 算法

Floyd–Warshall 依次允许更多顶点作为路径内部节点。无负圈时，第 $k$ 轮后，$d[i][j]$ 表示只使用前 $k$ 个允许中间点的最短距离；选取最优简单路后，它要么不经过新开放的 $k$，要么在唯一一次经过 $k$ 处拆成 $i⇝k$ 与 $k⇝j$ 两段。这个状态定义解释了为何三层循环中 $k$ 必须在最外层。

设 $d[1,2]=3$、$d[2,3]=-1$、$d[1,3]=5$。开放顶点 $2$ 作为中间点后，递推把 $d[1,3]$ 更新为 $2$；这里虽有负边却没有负圈，最优值可在有限条允许的简单路中取得。即使没有负圈，零权圈也可能产生无限多条等成本游走，因此不能靠“游走条数有限”来证明递推。若另有 $3\to 2$ 权 $-2$，则 $2\to 3\to 2$ 为负圈，所有能到达该圈且还能从圈到达的点对都应标为 $-\mathrm{\infty }$。

循环顺序必须让 $k$ 在最外层；随意交换三重循环会混入尚未开放的中间点，破坏状态不变量。要恢复具体有向路，可维护 next 或 predecessor 矩阵。存在相关负圈时，仅返回更新结束后的有限数值会误导，必须按可达条件传播 $-\mathrm{\infty }$ 或单独报告受影响点对。

Floyd–Warshall 是以允许的中间顶点集合为阶段的动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。。当输入用稠密矩阵表示，或确实需要全部 $n^2$ 个点对答案时，固定的 $O(n^3)$ 扫描常比逐源稀疏算法更合适；“稠密”是表示与复杂度条件，不改变输入的有向实权模型。布尔半环上同一递推得到传递闭包，替换代数运算还可计算最宽路等代数路径问题。

当图稀疏且无负环时，Johnson 算法理路Johnson 全源最短路算法Johnson's algorithm · Johnson all-pairs shortest paths以 Bellman–Ford 势函数把无负环图重赋为非负边权，再重复 Dijkstra 求稀疏图全源最短路。以势函数重赋权后从每点运行 Dijkstra，时间随 $m$ 而非固定 $n^3$；它与 Floyd–Warshall 的稠密矩阵 DP 是不同成本区域。布尔可达或小整数状态的某些矩阵转移可由四俄罗斯/字级并行理路四俄罗斯方法与字级并行Four Russians method · bit parallelism · broadword programming把状态切成可查表微块，或在一个机器字内并行处理多位，从而省去对数因子。分块加速，但必须说明字长和有限块类型，不能把普通实权 min-plus 更新无条件压成位运算。

距离积的倍增归约理路APSP与距离积的细粒度等价APSP min-plus equivalence · APSP与最小加乘积等价 · Distance product and APSP由三层有向图和距离矩阵倍增建立APSP与min-plus乘积的双向时间传递，明确整数位长、负环与输出边界。改以允许弧数1、2、4、…为阶段，给出另一种连接APSP与矩阵计算的方式；反向三层图可直接由本页算法求值。该等价说明速度怎样传递，不把某个时代的APSP困难性假设作为其证明前提。