没有合适的资源?快使用搜索试试~ 我知道了~
Bellman-Ford.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 44 浏览量
2023-02-27
19:44:04
上传
评论
收藏 304KB PDF 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/87509142/0001-c223ac25fbdb5ae85492cc3d6a684f8e_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
6页
。
资源推荐
资源详情
资源评论
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/87509142/bg1.jpg)
最短路径算法 —Bellman-Ford(贝尔曼 -福特 )
算法分析与实现(C/C++)
By
Tanky Woo
– 2011年01月17日 Posted in:我的原创|My Original Creation, 算法|Algorithms
相关文章:
1.Dijkstra 算法:
http://www.wutianqi.com/?p=1890
2.Floyd 算法:
http://www.wutianqi.com/?p=1903
Dijkstra 算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出
现权值为负的边,Dijkstra 算法就会失效,求出的最短路径就可能是错的。这时候,就需要
使用其他的算法来求解最短路径,Bellman-Ford 算法就是其中最常用的一个。该算法由美国
数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)
发明。Bellman-Ford 算法的流程如下:
给定图 G(V, E)(其中 V、E 分别为图 G 的顶点集与边集),源点 s,
数组 Distant[i]记录从源点 s 到顶点 i 的路径长度,初始化数组 Distant[n]为, Distant[s]
为0;
以下操作循环执行至多 n-1次,n 为顶点数:
对于每一条边 e(u, v),如果 Distant[u] + w(u, v) < Distant[v],则另 Distant[v] =
Distant[u]+w(u, v)。w(u, v)为边 e(u,v)的权值;
若上述操作没有对 Distant 进行更新,说明最短路径已经查找完毕,或者部分点不可达,
跳出循环。否则执行下次循环;
为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如
果存在 Distant[u] + w(u, v) < Distant[v] 的边,则图中存在负环路,即是说改图无法求出
单源最短路径。否则数组 Distant[n]中记录的就是源点 s 到各顶点的最短路径长度。
可知,Bellman-Ford 算法寻找单源最短路径的时间复杂度为 O(V*E).
首先介绍一下松弛计算。如下图:
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/a71a690a54794121897a1839eb6efba6_g11176593.jpg!1)
G11176593
- 粉丝: 6701
- 资源: 3万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)