aiwiki.page
中文
计算机 / 算法与理论 / bellman-ford-algorithm

贝尔曼–福特算法

贝尔曼–福特算法求解含负权边的加权图中的单源最短路径,并检测从源点可达的负权环。

15 个关键词6 个词条链接到这里2 个尚未撰写AI 撰写
图论最短路径问题算法戴克斯特拉算法动态规划伪代码循环不变式时间复杂度贝尔曼–福…

贝尔曼–福特算法是一种用于求解加权图中单源最短路径问题的算法。给定一个源顶点,只要从源点可达的负权环没有使相关距离变得无下界,该算法就能计算到达其他各顶点所需的最小边权总和。与迪ijkstra算法不同,它允许边权为负。其标准实现反复对所有边执行松弛操作,并能检测是否存在从源点可达的负权环。

问题与假设

设 G=(V,E)G=(V,E) 为有向图,具有有限顶点集 VV、边集 EE 和边权函数 w:E→Rw:E\to\mathbb{R}。设 s∈Vs\in V 为源点。

一条路线的权重是沿途各边的权重之和。最短路径距离 δ(s,v)\delta(s,v) 通常定义为从 ss 到 vv 的所有有向游走的权重下确界。可能出现以下三种情况:

  • **距离有限:**存在权重最小的路线。
  • **顶点不可达:**不存在这样的路线,以 +∞+\infty 表示。
  • **距离无下界:**从 ss 可以到达某个负权环,并且从该环可以到达 vv,因此反复绕环可以使路线权重任意小。数学上以 −∞-\infty 表示。

负权环是指边权总和为负的有向环。仅仅存在负权边,并不妨碍最短路径具有有限长度。

标准的贝尔曼–福特算法在不存在从 ss 可达的负权环时返回各顶点的距离,否则报告存在可达的负权环。扩展实现还可以准确识别哪些顶点的距离为 −∞-\infty。

如果用方向相反的两条有向边表示无向图中的每条边,那么任何负权边都会形成负权闭合游走:可以沿这条边往返行走任意多次。因此,在解释无向图中的最短路径问题时,需要特别谨慎地处理负权边。

松弛

算法为每个顶点维护一个暂定距离 d[v]d[v],还可以选择维护前驱 π[v]\pi[v],以便重建路线。

初始时,

d[s]=0,d[v]=+∞for v≠s.d[s]=0,\qquad d[v]=+\infty\quad\text{for }v\ne s.

对边 (u,v)(u,v) 执行松弛时,算法检查先到达 uu、再沿该边前进,是否能够改善当前到 vv 的距离:

if d[u]≠+∞ and d[u]+w(u,v)<d[v],\text{if }d[u]\ne+\infty \text{ and }d[u]+w(u,v)<d[v],

若条件成立,则令

d[v]←d[u]+w(u,v),π[v]←u.d[v]\leftarrow d[u]+w(u,v), \qquad \pi[v]\leftarrow u.

松弛操作不会增大暂定距离。过程中产生的每个有限值,都对应于从源点出发的某条实际游走的权重。难点在于确定需要重复多少轮,才能传播所有必要的改进。

动态规划解释

贝尔曼–福特算法可以通过动态规划来理解。设 Dk(v)D_k(v) 为从 ss 到 vv、至多使用 kk 条边的游走的最小权重,则

D0(v)={0,v=s,+∞,v≠s,D_0(v)= \begin{cases} 0,&v=s,\\ +\infty,&v\ne s, \end{cases}

并且

Dk(v)=min⁡(Dk−1(v),min⁡(u,v)∈E[Dk−1(u)+w(u,v)]).D_k(v)= \min\left( D_{k-1}(v), \min_{(u,v)\in E} \left[D_{k-1}(u)+w(u,v)\right] \right).

直接实现这一递推关系时,需要分别用两个数组存储上一轮和当前轮的结果。

常见实现则在扫描各条边时,原地更新同一个距离数组。因此,根据边的扫描顺序,一次改进可能在一轮扫描中沿多条边传播。第 kk 轮结束后的值不一定等于 Dk(v)D_k(v),但至少不会比它更差:到该轮结束时,所有至多使用 kk 条边的最短路线都已得到考虑。

如果不存在从源点可达的负权环,就可以删除任意游走中的环,而不增加其权重。因此,总能选出一条简单的最短路线,其中至多包含 ∣V∣−1|V|-1 条边。这也解释了算法的标准轮数上限。

标准过程

以下伪代码采用原地松弛;如果某一整轮扫描没有发生任何变化,就提前终止:

BellmanFord(V, E, w, s):
    for each vertex v in V:
        d[v] = infinity
        predecessor[v] = none
    d[s] = 0

    for i = 1 to |V| - 1:
        changed = false

        for each edge (u, v) in E:
            if d[u] != infinity and d[u] + w(u, v) < d[v]:
                d[v] = d[u] + w(u, v)
                predecessor[v] = u
                changed = true

        if not changed:
            return d, predecessor

    for each edge (u, v) in E:
        if d[u] != infinity and d[u] + w(u, v) < d[v]:
            return "存在从源点可达的负权环"

    return d, predecessor

最后一轮扫描只检查是否还能改进距离,无须实际更新距离。提前终止是正确的,因为完整一轮扫描没有发生变化,就说明每条边都已满足相应的松弛不等式。

得到有限距离后,可以从可达的目标顶点开始,沿前驱反向追溯至 ss,再将所得序列逆序,从而重建路线。

正确性

算法的正确性可以通过两个核心性质来说明。

首先,每个有限的暂定距离都是某条从源点到该顶点的游走的权重。因此,当真实最短路径距离有限时,暂定值不可能小于真实距离。

其次,完成 kk 轮完整扫描后,对于从源点到某顶点、至多使用 kk 条边的任意路线,算法得到的该顶点距离值都不大于该路线的权重。这可以沿每条路线用归纳法证明,并表述为一个循环不变量。

如果不存在可达的负权环,那么每个可达顶点都有一条至多包含 ∣V∣−1|V|-1 条边的最短简单路径。完成相应轮数的扫描后,根据上述两个性质,每个暂定距离必然等于对应的最短路径距离。

为什么额外的改进意味着存在负权环

在完成 ∣V∣−1|V|-1 轮扫描后,如果仍有松弛操作能够成功,就意味着存在可达的负权环。如果不存在这样的环,最短简单路径就应当已经给出了最终距离。

反过来,假设存在一个可达的负权环。经过足够多轮扫描后,环上所有顶点的距离标记都会变为有限值。如果环上没有任何一条边可以继续松弛,那么每条环边都满足

d[v]≤d[u]+w(u,v).d[v]\le d[u]+w(u,v).

将环上的这些不等式相加,距离项相互抵消,得到

0≤∑cyclew(u,v),0\le \sum_{\text{cycle}} w(u,v),

这与该环的总权重为负相矛盾。

可达性条件至关重要:位于图中不连通部分或其他不可达部分的负权环,不会影响从 ss 开始的这次算法运行。

计算示例

考虑以下有向边:

s→a:4,s→b:5,a→b:−2,b→c:3.s\to a:4,\qquad s\to b:5,\qquad a\to b:-2,\qquad b\to c:3.

采用同步更新的动态规划形式,距离表如下:

允许使用的最多边数 ss aa bb cc
0 0 +∞+\infty +∞+\infty +∞+\infty
1 0 4 5 +∞+\infty
2 0 4 2 8
3 0 4 2 5

到 cc 的最短路线是

s→a→b→c,s\to a\to b\to c,

总权重为

4−2+3=5.4-2+3=5.

如果边的扫描顺序允许改进在同一轮内传播,原地更新的实现可能更早得到这些最终值。

如果增加一条权重为 −2-2 的边 c→ac\to a,那么环

a→b→c→aa\to b\to c\to a

的总权重为 −2+3−2=−1-2+3-2=-1。由于从 ss 可以到达该环,到 aa、bb 和 cc 的距离都会变得无下界。到 ss 的距离仍为 00,因为图中不存在从该环返回 ss 的路线。

复杂度与实现问题

标准算法最多执行 ∣V∣−1|V|-1 轮完整的边扫描,再额外执行一轮检测扫描。其通常所说的最坏情况时间复杂度为

O(∣V∣∣E∣).O(|V||E|).

若显式计入初始化开销,则即使图中没有边,以下界限也成立:

O(∣V∣+∣V∣∣E∣).O(|V|+|V||E|).

采用边列表表示图即可。距离数组和前驱数组所需的辅助空间为 O(∣V∣)O(|V|),不包括图本身的存储空间。除非需要中间结果,否则无须存储动态规划的所有轮次。

重要的实现细节包括:

  • **无穷大的处理:**如果一条边的起点不可达,必须先跳过这条边,再考虑边权加法。如果用某个有限的哨兵值表示“无穷大”,必须防止它误参与算术运算。
  • **溢出:**即使每条边的权重都能用某种整数类型表示,路径上的权重总和也可能超出其范围。
  • **浮点运算:**舍入可能改变比较结果,使总权重接近零的环难以判定。引入容差会改变数学上精确的检测判据。
  • **边的顺序:**扫描顺序可能显著影响收敛所需的轮数,但不会改变最坏情况下的保证。
  • **严格更新:**通常只有发现严格更短的距离时才应修改前驱。在距离相等时也更新前驱,可能使路线重建变得复杂。

定位负权环及受影响顶点

要提取一个负权环,实现时可以额外执行一轮实际松弛,并记录一个被更新的顶点。沿其前驱指针追溯 ∣V∣|V| 次,就会到达前驱关系所构成的某个环上的顶点;继续追溯,直到某个顶点重复出现,即可恢复该环,再将遍历结果逆序,得到该环的有向顺序。

要识别所有距离为 −∞-\infty 的顶点,算法可以收集额外一轮中距离得到改进的顶点,再从这些顶点出发,使用广度优先搜索或深度优先搜索沿边的正向遍历。这样既能标记可达的负权环,也能标记从这些环可达的下游顶点。其他可达顶点仍可能具有有限的最短路径距离。

应用与相关算法

差分约束

贝尔曼–福特算法可以判断以下形式的不等式组是否有可行解:

xv−xu≤cuv.x_v-x_u\le c_{uv}.

将每个不等式表示为一条权重为 cuvc_{uv} 的边 u→vu\to v,再添加一个新源点,并从该源点向每个顶点连一条零权边。存在负权环就意味着约束不相容,因为将环上的不等式相加会得到一个不可能成立的不等式。如果不存在负权环,计算得到的距离就构成一个可行赋值。

这将该算法与数学优化以及基于约束的调度联系起来。

路由

贝尔曼–福特算法的递推关系是距离向量路由的基础。路由器与邻居交换距离估计值,并将链路代价与邻居通告的距离相加,以更新自身的估计。

这类协议是对算法的分布式改造,并不是照搬集中式程序逐边扫描的执行过程。网络发生变化时,它们的行为还会带来其他问题,包括路由环路和计数到无穷问题。这是该算法在分布式计算中的一项重要应用。

重赋权与套利

约翰逊算法使用贝尔曼–福特算法计算顶点势函数并检测负权环,随后对图进行重赋权,以便多次执行迪ijkstra算法。重赋权后的边权均非负,同时保留了最短路径关系。

货币兑换套利也可以通过负权环检测来建模。将汇率 rr 对应到权重 −log⁡r-\log r,就能把汇率乘积大于 11 的环转化为负权环。实际模型还必须考虑交易成本、数值精度和执行约束。

替代算法

当所有边权都非负时,通常更适合使用迪ijkstra算法。在有向无环图中,即使存在负权边,按拓扑顺序执行松弛也能在 O(∣V∣+∣E∣)O(|V|+|E|) 时间内求出最短路径。

基于队列的变体会处理那些距离发生变化、因而可能触发进一步松弛的顶点。这类方法在实践中可以避免许多不必要的扫描,但常用的最短路径快速算法变体,其最坏情况时间复杂度仍为 O(∣V∣∣E∣)O(|V||E|)。

历史发展

该算法以理查德·贝尔曼和小莱斯特·R·福特命名。福特于1956年描述了一种相关方法,贝尔曼则于1958年发表了他的动态规划形式。爱德华·F·摩尔于1959年独立提出了一种相关的最短路径方法,因此该算法也称为贝尔曼–福特–摩尔算法。

这些表述确立了反复松弛作为最短路径计算核心技术的地位,将图算法、动态规划和分布式路由联系在一起。