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 更新无条件压成位运算。