没有合适的资源?快使用搜索试试~ 我知道了~
Bellman-Ford算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 54 浏览量
2022-05-06
15:08:45
上传
评论
收藏 16KB DOCX 举报
温馨提示
试读
2页
Bellman-Ford算法.docx
资源推荐
资源详情
资源评论
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 算法的伪代码如下:
[Copy to clipboard]View Code PASCAL1
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 Vbr Distance(v) = +∞brDistance(s) = 0br ∈ 循环 n-1 次 br for 每一条路径
( u,v ) ∈ Ebr if Distance(u) + weight(u,v) Distance(v) thenbr Distance(v) = Distance(u) +
weight(u,v)br for 每一条路径 (u,v)属于 Ebr if Distance(u) + weight(u,v) Distance(v) br then
中止程序并且返回 “找到负循环”br 返回 执行成功 br
第一次迭代时,Distance(s)=0,而对于任意 v V ∈ 且 v s,Distance(v)=+∞。因此第一次执行
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功