Bellman-Ford 算法如何处理负权边？怎么判断负环？

简化版

Bellman-Ford 是单源最短路径算法，可以处理负权边。

它的核心是对所有边反复松弛 V - 1 轮，因为一条没有环的最短路径最多包含 V - 1 条边。如果第 V 轮还能继续松弛，说明存在从源点可达的负权环，最短路径可以被无限变小。

它比 Dijkstra 慢，但适合有负权边和需要检测负环的场景。

详细版

Bellman-Ford 维护 dist[v]，表示从源点到 v 的当前最短距离。

每一轮遍历所有边：

if dist[u] + w < dist[v]:
  dist[v] = dist[u] + w

做 V - 1 轮后，如果不存在负环，所有最短路径都已经稳定。

算法	能否处理负权边	能否检测负环	复杂度
Dijkstra	不能稳妥处理	不能直接判断	`O(E log V)`
Bellman-Ford	可以	可以	`O(VE)`

面试回答重点：负权边不等于负环，Bellman-Ford 能处理前者，也能检测后者。

完整版教学

1. 为什么 Dijkstra 遇到负权边会出问题

Dijkstra 的贪心前提是：当前取出的最小距离节点，以后不会再被更新。

这个前提依赖边权非负。因为后面再绕一条边，只会让路径更长或相等。

一旦有负权边，某个已经确定的节点可能被后续路径重新变小，贪心就不可靠。

负权边会破坏 Dijkstra 的“已确定节点不再变小”这个关键假设。

2. Bellman-Ford 的基本思想

Bellman-Ford 不急着确定某个节点。

它反复遍历所有边，只要发现更短路径就更新。

for i in 1..V-1:
  for each edge (u, v, w):
    relax(u, v, w)

这种做法更朴素，也更稳。它不依赖边权非负，所以能处理负权边。

3. 为什么是 V - 1 轮

如果图中不存在负环，一条最短路径不会重复经过同一个点。

如果重复经过某个点，就形成环。非负或正环可以去掉；负环则会让最短路径不存在有限值。

所以正常最短路径最多包含：

V - 1 条边

每一轮松弛可以理解成允许路径多使用一条边。经过 V - 1 轮后，所有简单路径都被考虑到了。

4. 如何判断负环

在完成 V - 1 轮后，再额外遍历一轮所有边。

如果仍然存在：

dist[u] + w < dist[v]

说明还可以继续变短。既然简单路径最多只有 V - 1 条边，继续变短只能说明路径里出现了负权环。

第几轮	含义
前 `V - 1` 轮	计算最短路径
第 `V` 轮	检测是否还能松弛

5. 负环必须从源点可达吗

如果做的是单源最短路径，只有从源点可达的负环才会影响结果。

如果某个负环在另一个不连通分量中，源点到不了它，它不会影响源点出发的最短路径。

因此判断时通常要求：

dist[u] != INF

只有 u 可达，边 (u, v) 的松弛才有意义。

6. 伪代码怎么写

完整伪代码可以这样表达：

dist[source] = 0
for all other v: dist[v] = INF

repeat V - 1 times:
  for edge in edges:
    if dist[edge.u] != INF and dist[edge.u] + edge.w < dist[edge.v]:
      dist[edge.v] = dist[edge.u] + edge.w

for edge in edges:
  if dist[edge.u] != INF and dist[edge.u] + edge.w < dist[edge.v]:
    hasNegativeCycle = true

这段代码的重点是边集遍历，不需要优先队列。

7. 适合什么场景

Bellman-Ford 适合：

场景	原因
图中有负权边	Dijkstra 不稳
要检测负环	第 `V` 轮可以判断
点边规模不大	`O(VE)` 可接受
约束差分系统	可转成最短路径和负环判断

如果所有边权非负，优先考虑 Dijkstra。

8. 常见误区与追问

误区：有负权边就一定没有最短路径。 负权边可以有最短路径，真正让最短路径失效的是可达负环。
误区：Bellman-Ford 只要跑 V 轮。 前 V - 1 轮求解，第 V 轮用于检测负环，含义不同。
误区：任意负环都会影响单源最短路径。 只有源点可达的负环才影响该源点结果。
追问：为什么复杂度是 O(VE)？ 外层约 V 轮，内层遍历所有 E 条边。
追问：什么时候不用 Bellman-Ford？ 边权非负且规模较大时，Dijkstra 通常更合适。

简化版

详细版