形式陈述

Floyd–Warshall 求所有点对最短路。令 $D^{(k)}[i,j]$ 为只允许中间顶点来自 $\{1,\dots ,k\}$ 的最短距离，则

$$D^{(k)}[i,j]=min\{D^{(k-1)}[i,j],D^{(k-1)}[i,k]+D^{(k-1)}[k,j]\}.$$

按 $k$ 外层原地更新矩阵即可，时间 $\mathrm{\Theta }(|V{|}^3)$、空间 $\mathrm{\Theta }(|V{|}^2)$。初值为边权，$D[i,i]=0$，无边为 $+\mathrm{\infty }$。若最终某个 $D[i,i]<0$，则存在可达于自身的负环。

直觉

任一最短路径要么不用新允许的中间点 $k$，要么第一次分解为 $i⇝k$ 与 $k⇝j$ 两段；动态规划逐个开放中间顶点。

例子与边界

三顶点中即使直接边 $i\to j$ 权 10，经 $k$ 两段权 3 和 4，更新后变为 7。循环顺序必须让 $k$ 在最外层；随意交换三重循环会破坏“已允许中间点集合”的不变量。含负边但无负环时算法仍正确。若要恢复路径，可维护 next 或 predecessor 矩阵。负环存在时，某些点对的真实下确界为 $-\mathrm{\infty }$，原矩阵中的有限数不再是有意义最短值，需要额外传播受影响范围。

推论与应用

Floyd–Warshall 适合稠密图、传递闭包、最短路径矩阵和小规模动态网络，也是 min-plus 代数与区间动态规划的经典实例。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。