-
核心概述 在允许负权边的图上，从源点 s 计算最短路，支持不可达标记与负环可达域的 -inf 标记，时间 O(VE)。
-
原文引述
Description: Calculates shortest paths from in a graph that might have negative edge weights. Unreachable nodes get dist = inf; nodes reachable through negative-weight cycles get dist = -inf. Time: O(VE)
- 展开阐述
-
定义与背景
- 目标：在一般有向/无向（按输入建边）带权图中，从单源 s 求最短距离；允许存在负权边。
- 能力边界：若存在可以从 s 到达的负环，则该负环可达的所有点最短路“无下界”，约定距离为 -inf；不可达点为 inf。
-
数据结构与接口（据实现约定）
- 边结构 Ed：字段 a, b, w；并有 s() 返回 |a| 的排序键（仅用于实现中的处理顺序）。
- 点结构 Node：dist 初始化为 inf，prev 记录前驱索引（用于还原路径）。
- 入口：bellmanFord(nodes, eds, s)
- nodes：顶点数组（含 dist/prev）
- eds：边数组
- s：源点索引
-
核心流程/要点（BF + 负环影响传播）
- 初始化
- dist[s]=0，其他为 inf。
- 可按实现对边按 s() 排序以获得稳定的松弛顺序（非必要正确性条件）。
- 主循环（有限轮松弛）
- 令 lim = |V|/2 + 2（或实现注释给出的 |V|/3 + 100 搭配随机顶点序），进行 lim 轮扫描：
- 前 lim−1 轮：对每条边 (a→b, w)，若 dist[a] 非 inf 且 dist[b] > dist[a]+w，则更新 dist[b]=dist[a]+w、prev[b]=a。
- 第 lim 轮：若仍可松弛某条边 (a→b)，则将 b 置为 -inf，用于“标记负环影响”。
- 令 lim = |V|/2 + 2（或实现注释给出的 |V|/3 + 100 搭配随机顶点序），进行 lim 轮扫描：
- 负环影响的额外传播
- 再次遍历所有边：若 dist[a]==-inf，则强制 dist[b]=-inf，以把“负环可达性”在一跳内扩散；重复或在若干次扫描中传遍整个可达域（实现可一次性完成，具体以代码为准）。
- 路径还原（可选）
- 对 dist[x] 为有限数的点，可沿 prev 回溯得到一条最短路；对 -inf/inf 的点不定义确定路径。
- 不变式与正确性直觉
- 在无负环影响的情况下，进行至多 |V|−1 轮边松弛后，dist 已为最短路值；若第 |V| 轮仍可改进，说明存在可达负环。
- 用 -inf 将“可被任意次绕环继续变短”的点域显式标注，避免输出无意义的有限数。
- 初始化
-
复杂度与边界条件
- 时间：O(VE)，空间：O(V)。
- 多源：可添加超级源连到所有源点，边权为 0。
- 不可达：dist 维持为 inf。
- 自环/重边：不影响正确性，按松弛规则自然处理。
- 权值上界：实现中假设 V^2·max|w| 小于 64 位上界，以免溢出。
- 图向：常用有向图；无向图可将每条无向边拆为两条反向边。
-
变体/扩展与对比
- SPFA：基于队列的松弛顺序优化，通常更快，但最坏仍 O(VE)；实现与数据分布敏感，易被卡。
- Dijkstra：更快 O((E+V)logV)，但不允许负权边；若权值均非负，应优先选择。
- Floyd–Warshall：全源最短路 O(V^3)，适合小图且需要任意两点距离（见 062-图论-FloydWarshall）。
-
工程要点
- -inf 标记语义需与输出/评测一致：负环可达域统一置 -inf；避免与“非常小的有限数”混淆。
- 终止策略：在某轮扫描没有任何更新时可提前结束（若未启用 -inf 判定的第 lim 轮，可直接判定收敛）。
- 关联节点