Floyd–WarshallFloyd–Warshall

逐个加入允许使用的中间顶点，更新所有顶点对距离。

核心约束: 第 k 轮只允许前 k 个顶点作为内部中间点。
适用问题: 需要全部顶点对距离、顶点数适中的图；允许负权边。
边界与取舍: 若 u 能到达某个负环且该负环能到达 v，u 到 v 没有有限最短距离；负对角项可检测负环。还需处理不可达哨兵与加法溢出。

时间与空间#

V 为顶点数；距离矩阵含所有顶点对。

时间复杂度: $O(V^{3})$
辅助空间: $O(V^{2})$ ，保存全对距离；路径恢复再用 $O(V^{2})$

按中间顶点逐层更新，允许负边但有限最短路要求不存在相关负环。处理“无穷大”时避免溢出；对角线出现负值可用于检测负环。

基础原理参考资料

Boost.Graph 1.85 · Floyd–Warshall全点对距离矩阵、负环语义及三次时间。