-
YAML 元数据 已设置 tags: [KACTL, 图论, 核心概念]。
-
核心概述 在小规模图上以三重循环 O(N^3) 计算任意两点最短路，允许负权并将所有经过负环可达的点对距离标记为 -inf。
-
原文引述
Description: Calculates all-pairs shortest path in a directed graph that might have negative edge weights. Time: O(N^3)
- 展开阐述
-
定义与背景
- 目标：给定有向图的距离矩阵 m，返回所有点对 (i,j) 的最短距离；若 i→j 不可达则为 inf；若存在路径经过负权环使距离可无界减小，则记为 -inf。
- 典型场景：需要全源最短路或频繁多对查询的小图；作为传递闭包/负环检测与传播的基础模块。
-
接口/数据结构（据实现约定）
- 输入：m 为距离矩阵（m[i][j]=inf 表示无边）；常取 inf=1LL<<62。
- 初始化：对角线 m[i][i] = min(m[i][i], 0)，允许自环负边覆盖更小值。
- 输出：就地更新 m，完成最短路、不可达与负环域（-inf）的统一语义。
-
核心流程/要点（k 作为“中间点”的动态规划）
- 三重循环松弛
- for k in [0..n): for i,j: 若 m[i][k]、m[k][j] 有限，则 m[i][j] = min(m[i][j], m[i][k] + m[k][j])。
- 加法前务必判定有限以避免溢出或无效比较。
- 负环检测与影响传播
- 若 m[k][k] < 0，存在经过 k 的负环。
- 对所有 i,j：若 m[i][k]、m[k][j] 有限，则将 m[i][j] 置为 -inf（一次或两次额外循环传播，确保“经任一负环可达”的对被标注）。
- 不可达保持
- i 无法到达 j 的情形，m[i][j] 维持为 inf。
- 三重循环松弛
-
复杂度与边界条件
- 时间/空间：O(N^3)/O(N^2)。
- 权值：允许负权；重边按最小权自然生效；自环可参与负环判定。
- 数值安全：对 inf 做短路判断，避免 inf + 有限 导致溢出或伪优。
- 路径重构：可维护 next/pre 矩阵进行路径还原，需 O(N^2) 额外空间。
-
变体/扩展与关系
- Warshall 传递闭包：将“加/取最小”替换为“与/或”得到可达性闭包。
- 半环推广：在一般 (⊕,⊗) 代数结构下作为闭包运算模板。
- 对比：与 052-图论-贝尔曼福德（单源、可判负环）、Dijkstra（非负权时更快）互补；当仅需少量源点时更宜选单/多源算法。
-
正确性要点与不变式
- 第 k 轮后，m[i][j] 等价于仅允许使用 {0..k} 中间点的最短路值；由归纳可得最终收敛。
- 若存在 m[k][k]<0，则任何经 k 可达的 i→j 可被负环无限改善，故以 -inf 表示其下界趋于 -∞。
-
与相邻技术的对比与取舍建议
- 规模与密度：N 较小且需全源最短路时选 FW；大图或仅少量源点选 Bellman-Ford/Dijkstra/多源队列法。
- 负环处理：FW 可一次性得到所有负环影响域；若仅需检测某源的负环影响，单源算法足矣。
- 关联节点