Bellman-Ford 算法(带权有向图最短路径算法)

Bellman-Ford算法(根据发明者 Richard Bellman 和 Lester Ford 命名)是求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore 也为这个算法的发展做出了贡献。
单源点的最短路径问题是指:给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。
与迪杰斯特拉算法,(另一种著名的求最短路径的算法)不同的是,在 Bellman-Ford 算法中,路径的权值可以为负数。 设想从我们可以从图中找到一个环路(即从v出发,经过若干个点之后又回到v)且这个环路中所有路径的权值之和为负。那么通过这个环路,环路中任意两点的最 短路径就可以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

算法描述

设G为加权有向图 V是所有结点的集合 E是所有路径的集合 S表示源点 n表示V中所有结点的数目 weight(u,v)表示从结点u到结点v的路径的权值。 Distanz(v)表示从源点s出发到结点v的最短路径的距离,(或者说是从s到v所有的路径中权值的最小值)。【Predecessor(v)表示节 点v的父结点。】在Bellman-Ford算法结束之后,可以输出,G是不是包含一个负环路。如果G不包含负环路,那么Distanz就存储了从s出发 到所有结点的距离。

Bellman-Ford 算法是 SPFA 算法的基础算法。SPFA 算法是 Bellman-Ford 算法的加强版,时间复杂度和适用面都优于 Dijkstra 算法。设G = (V,E,W) 为某一有向带权图(W 即 weight,权值),s,t 分别代表源点和终点,Distance(v) 代表 v 在算法当前阶段中暂定的从源点出发的最短权和,则算法的核心思想是进行至多 |V|-1 次的迭代处理,每次从 s 出发扩展一层路径,逐渐逼近最短路径。

Bellman-Ford算法的伪代码如下:

for 每一个结点v ∈ V
   Distance(v) := +∞
Distance(s) := 0
 循环 n-1 次
     for 每一条路径 (u,v)∈ E
         if Distance(u) + weight(u,v) < Distance(v) then
            Distance(v) := Distance(u) + weight(u,v)
 for 每一条路径 (u,v)属于 E
     if Distance(u) + weight(u,v) < Distance(v)
     then 中止程序并且返回 「找到负循环」
 返回 执行成功

for 每一个结点v ∈ V
Distance(v) := +∞
Distance(s) := 0
循环 n-1 次
for 每一条路径 (u,v)∈ E
if Distance(u) + weight(u,v) < Distance(v) then
Distance(v) := Distance(u) + weight(u,v)
for 每一条路径 (u,v)属于 E
if Distance(u) + weight(u,v) < Distance(v)
then 中止程序并且返回 「找到负循环」
返回 执行成功

第一次迭代时,Distance(s)=0,而对于任意 v ∈ V 且 v <> s,Distance(v)=+∞。因此第一次执行时,从伪代码可以看出,该算法实质是找到了从点 s 出发的所有边并更新了这些边的其非源端点到源点的Distance距离为这些边本身的权值。

第二次迭代时,对于所有 Distance(v) 不为无穷大的非源点,其 Distance 值即是从 s 出发的某条边的权值。在这次迭代中,在进行

 if Distance(u) + weight(u,v) < Distance(v)
         then
            Distance(v) := Distance(u) + weight(u,v) 

if Distance(u) + weight(u,v) < Distance(v)
then
Distance(v) := Distance(u) + weight(u,v)

即 更新 Distance 的值的过程中,新得到的 Distance(v) 由两部分组成,一部分是 Distance(u),上文已说明它们中存储的是从点 s 出发的各个边的权值,一部分是 weight(u,v),也即 Distance(v) 中最终存储的是从 s 出发的经过两层(两条边)到达 v 的路径长度。

以此类推,每次执行迭代后,均为按层扩展(或称增广),每次都可能更新 Distance(v),其实质是通过更多层数换取更小的权值,经过了最多 |V|-1 次的增广,即可保证得到了从 s 出发到任意一个点的最短路径,并存储在了 Distance(v) 中。

如有任何疑问或对本文所述内容有任何不解或本文发现错误,敬请提出或批评指正。

题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: