专题进阶 · 图算法推荐总顺序 · 第 57 / 148 课

用边数分层解释反复松弛,检测从源点可达的负环。

先学会这些,再进入本课 Dijkstra
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

Bellman–FordBellman–Ford

反复松弛所有边,可处理负权并检测从源点可达的负环。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用边数分层解释反复松弛,检测从源点可达的负环。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

有向边 0→1 权 4、0→2 权 5、1→2 权 −2。负边会让 Dijkstra 的确定步骤失效,怎样仍求最短路?

02一步步得到方法

先取消过早确定的承诺

Bellman–Ford 不把某个节点永久定案,而是反复检查每条边:若 dist[u]+w<dist[v],就改进 v。初始化源点为 0,其余正无穷;不可达点不能作为有效松弛起点。

按轮次理解:第 k 轮结束后,所有最多使用 k 条边的可达路径的最优值已经能被传播到。代码若原地更新,单轮可能传播更多边,但不会比这个保证更差。

为什么 V−1 轮足够

没有可达负环时,最短路可取不重复节点的简单路径,最多 V−1 条边。完成这些轮后再检查一轮,若仍可改进,就有从源点可达的负环。

负环可被反复绕行使路径代价无限下降,相关目标不存在有限最短值。本课返回 None 表示发现这种情况,不返回看似正常的有限数组。与源点不连通的负环不会影响这次单源结果。

把轮数解释为路径边数

同步版本第 k 轮在上一轮结果上扩展一条边,可解释为最多 k 条边的最短距离。原地松弛同一轮可能传播多条边,但 n−1 轮的充分性仍可由简单最短路径至多含 n−1 条边来理解。

只从已可达端点进行松弛,避免把无穷距离与负权相加误当有效路径。若第 n 轮仍能从可达部分改善,就存在影响相关路径的负环;若要求逐节点标记,还需从受影响点继续传播。

03把一个小例子完全算清楚

3 点有向图:0→1:4,0→2:5,1→2:−2。

步骤计算与状态为什么这样做
初始化[0,∞,∞]只知道源点
扫描第一轮[0,4,2]经 1 到 2 的代价为 4−2=2
下一轮无变化可以提前终止
额外检查没有边可再改进无可达负环

窄屏可左右滑动表格,阅读完整计算与理由。

允许负边不等于允许负环下仍有有限答案。

04为什么这个方法成立

  1. 每次更新都对应一条真实可达路径,所以不会凭空得到不存在的更短值。
  2. 逐轮松弛覆盖最多 k 条边路径,V−1 轮覆盖所有简单路径。
  3. 若此后还可改进,改进路径必重复节点,其中包含可降低代价的负环。

05把推导翻译成代码

Python · 可独立运行的教学实现

def bellman_ford(n, edges, source):
    dist = [float("inf")]*n
    dist[source] = 0
    for _ in range(n-1):
        changed = False
        for u,v,w in edges:
            if dist[u] != float("inf") and dist[u]+w < dist[v]:
                dist[v] = dist[u]+w
                changed = True
        if not changed:
            break
    for u,v,w in edges:
        if dist[u] != float("inf") and dist[u]+w < dist[v]:
            return None
    return dist

逐个理解关键决定

dist[u] != float("inf")
保证只传播源点可达路径,也使负环检测范围明确。
if not changed
整轮没有改进后已达不动点,后续轮不会产生新信息。

06时间、空间与实现范围

最坏时间 O(VE),距离数组 O(V),输入边表 O(E)。

想恢复路径需记录 predecessor;发现负环后若要标出受影响目标,还需从环向外搜索。

07改变条件,检查哪里会出错

只要图里有任意负环就否定所有单源结果

不连通负环不影响当前源点;必须检查可达性。

检测到可达负环就声称每个节点距离都无穷小

只有可从该负环继续到达的节点受到影响;其他可达分支可能仍有有限最短距离。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

0→1:1、1→0:−2 有什么问题?

需要一点提示

绕一圈成本。

查看解析与答案

环成本 −1,可无限降低源点可达节点距离,返回 None。

练习 2 · 边界与辨析

无负边时为何仍可能选 Dijkstra?

需要一点提示

比较时间界。

查看解析与答案

Bellman–Ford 更一般但通常更慢;非负前提允许 Dijkstra 更高效地确定节点。

练习 3 · 变式与迁移

无向图里一条负边意味着什么?

需要一点提示

边可来回走。

查看解析与答案

按可重复走边的最短路定义,来回形成负成本闭游走,距离可无限下降。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。