贝尔曼–福特算法是一种用于求解加权图中单源最短路径问题的算法。给定一个源顶点,只要从源点可达的负权环没有使相关距离变得无下界,该算法就能计算到达其他各顶点所需的最小边权总和。与迪ijkstra算法不同,它允许边权为负。其标准实现反复对所有边执行松弛操作,并能检测是否存在从源点可达的负权环。
问题与假设
设 为有向图,具有有限顶点集 、边集 和边权函数 。设 为源点。
一条路线的权重是沿途各边的权重之和。最短路径距离 通常定义为从 到 的所有有向游走的权重下确界。可能出现以下三种情况:
- **距离有限:**存在权重最小的路线。
- **顶点不可达:**不存在这样的路线,以 表示。
- **距离无下界:**从 可以到达某个负权环,并且从该环可以到达 ,因此反复绕环可以使路线权重任意小。数学上以 表示。
负权环是指边权总和为负的有向环。仅仅存在负权边,并不妨碍最短路径具有有限长度。
标准的贝尔曼–福特算法在不存在从 可达的负权环时返回各顶点的距离,否则报告存在可达的负权环。扩展实现还可以准确识别哪些顶点的距离为 。
如果用方向相反的两条有向边表示无向图中的每条边,那么任何负权边都会形成负权闭合游走:可以沿这条边往返行走任意多次。因此,在解释无向图中的最短路径问题时,需要特别谨慎地处理负权边。
松弛
算法为每个顶点维护一个暂定距离 ,还可以选择维护前驱 ,以便重建路线。
初始时,
对边 执行松弛时,算法检查先到达 、再沿该边前进,是否能够改善当前到 的距离:
若条件成立,则令
松弛操作不会增大暂定距离。过程中产生的每个有限值,都对应于从源点出发的某条实际游走的权重。难点在于确定需要重复多少轮,才能传播所有必要的改进。
动态规划解释
贝尔曼–福特算法可以通过动态规划来理解。设 为从 到 、至多使用 条边的游走的最小权重,则
并且
直接实现这一递推关系时,需要分别用两个数组存储上一轮和当前轮的结果。
常见实现则在扫描各条边时,原地更新同一个距离数组。因此,根据边的扫描顺序,一次改进可能在一轮扫描中沿多条边传播。第 轮结束后的值不一定等于 ,但至少不会比它更差:到该轮结束时,所有至多使用 条边的最短路线都已得到考虑。
如果不存在从源点可达的负权环,就可以删除任意游走中的环,而不增加其权重。因此,总能选出一条简单的最短路线,其中至多包含 条边。这也解释了算法的标准轮数上限。
标准过程
以下伪代码采用原地松弛;如果某一整轮扫描没有发生任何变化,就提前终止:
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
最后一轮扫描只检查是否还能改进距离,无须实际更新距离。提前终止是正确的,因为完整一轮扫描没有发生变化,就说明每条边都已满足相应的松弛不等式。
得到有限距离后,可以从可达的目标顶点开始,沿前驱反向追溯至 ,再将所得序列逆序,从而重建路线。
正确性
算法的正确性可以通过两个核心性质来说明。
首先,每个有限的暂定距离都是某条从源点到该顶点的游走的权重。因此,当真实最短路径距离有限时,暂定值不可能小于真实距离。
其次,完成 轮完整扫描后,对于从源点到某顶点、至多使用 条边的任意路线,算法得到的该顶点距离值都不大于该路线的权重。这可以沿每条路线用归纳法证明,并表述为一个循环不变量。
如果不存在可达的负权环,那么每个可达顶点都有一条至多包含 条边的最短简单路径。完成相应轮数的扫描后,根据上述两个性质,每个暂定距离必然等于对应的最短路径距离。
为什么额外的改进意味着存在负权环
在完成 轮扫描后,如果仍有松弛操作能够成功,就意味着存在可达的负权环。如果不存在这样的环,最短简单路径就应当已经给出了最终距离。
反过来,假设存在一个可达的负权环。经过足够多轮扫描后,环上所有顶点的距离标记都会变为有限值。如果环上没有任何一条边可以继续松弛,那么每条环边都满足
将环上的这些不等式相加,距离项相互抵消,得到
这与该环的总权重为负相矛盾。
可达性条件至关重要:位于图中不连通部分或其他不可达部分的负权环,不会影响从 开始的这次算法运行。
计算示例
考虑以下有向边:
采用同步更新的动态规划形式,距离表如下:
| 允许使用的最多边数 | ||||
|---|---|---|---|---|
| 0 | 0 | |||
| 1 | 0 | 4 | 5 | |
| 2 | 0 | 4 | 2 | 8 |
| 3 | 0 | 4 | 2 | 5 |
到 的最短路线是
总权重为
如果边的扫描顺序允许改进在同一轮内传播,原地更新的实现可能更早得到这些最终值。
如果增加一条权重为 的边 ,那么环
的总权重为 。由于从 可以到达该环,到 、 和 的距离都会变得无下界。到 的距离仍为 ,因为图中不存在从该环返回 的路线。
复杂度与实现问题
标准算法最多执行 轮完整的边扫描,再额外执行一轮检测扫描。其通常所说的最坏情况时间复杂度为
若显式计入初始化开销,则即使图中没有边,以下界限也成立:
采用边列表表示图即可。距离数组和前驱数组所需的辅助空间为 ,不包括图本身的存储空间。除非需要中间结果,否则无须存储动态规划的所有轮次。
重要的实现细节包括:
- **无穷大的处理:**如果一条边的起点不可达,必须先跳过这条边,再考虑边权加法。如果用某个有限的哨兵值表示“无穷大”,必须防止它误参与算术运算。
- **溢出:**即使每条边的权重都能用某种整数类型表示,路径上的权重总和也可能超出其范围。
- **浮点运算:**舍入可能改变比较结果,使总权重接近零的环难以判定。引入容差会改变数学上精确的检测判据。
- **边的顺序:**扫描顺序可能显著影响收敛所需的轮数,但不会改变最坏情况下的保证。
- **严格更新:**通常只有发现严格更短的距离时才应修改前驱。在距离相等时也更新前驱,可能使路线重建变得复杂。
定位负权环及受影响顶点
要提取一个负权环,实现时可以额外执行一轮实际松弛,并记录一个被更新的顶点。沿其前驱指针追溯 次,就会到达前驱关系所构成的某个环上的顶点;继续追溯,直到某个顶点重复出现,即可恢复该环,再将遍历结果逆序,得到该环的有向顺序。
要识别所有距离为 的顶点,算法可以收集额外一轮中距离得到改进的顶点,再从这些顶点出发,使用广度优先搜索或深度优先搜索沿边的正向遍历。这样既能标记可达的负权环,也能标记从这些环可达的下游顶点。其他可达顶点仍可能具有有限的最短路径距离。
应用与相关算法
差分约束
贝尔曼–福特算法可以判断以下形式的不等式组是否有可行解:
将每个不等式表示为一条权重为 的边 ,再添加一个新源点,并从该源点向每个顶点连一条零权边。存在负权环就意味着约束不相容,因为将环上的不等式相加会得到一个不可能成立的不等式。如果不存在负权环,计算得到的距离就构成一个可行赋值。
这将该算法与数学优化以及基于约束的调度联系起来。
路由
贝尔曼–福特算法的递推关系是距离向量路由的基础。路由器与邻居交换距离估计值,并将链路代价与邻居通告的距离相加,以更新自身的估计。
这类协议是对算法的分布式改造,并不是照搬集中式程序逐边扫描的执行过程。网络发生变化时,它们的行为还会带来其他问题,包括路由环路和计数到无穷问题。这是该算法在分布式计算中的一项重要应用。
重赋权与套利
约翰逊算法使用贝尔曼–福特算法计算顶点势函数并检测负权环,随后对图进行重赋权,以便多次执行迪ijkstra算法。重赋权后的边权均非负,同时保留了最短路径关系。
货币兑换套利也可以通过负权环检测来建模。将汇率 对应到权重 ,就能把汇率乘积大于 的环转化为负权环。实际模型还必须考虑交易成本、数值精度和执行约束。
替代算法
当所有边权都非负时,通常更适合使用迪ijkstra算法。在有向无环图中,即使存在负权边,按拓扑顺序执行松弛也能在 时间内求出最短路径。
基于队列的变体会处理那些距离发生变化、因而可能触发进一步松弛的顶点。这类方法在实践中可以避免许多不必要的扫描,但常用的最短路径快速算法变体,其最坏情况时间复杂度仍为 。
历史发展
该算法以理查德·贝尔曼和小莱斯特·R·福特命名。福特于1956年描述了一种相关方法,贝尔曼则于1958年发表了他的动态规划形式。爱德华·F·摩尔于1959年独立提出了一种相关的最短路径方法,因此该算法也称为贝尔曼–福特–摩尔算法。
这些表述确立了反复松弛作为最短路径计算核心技术的地位,将图算法、动态规划和分布式路由联系在一起。