辽宁智能建站系统价格,如何做本地门户网站,免费私人网站建设,广州网站建设高端Flyer 目录视图摘要视图订阅 微信小程序实战项目——点餐系统 程序员11月书讯#xff0c;评论得书啦 Get IT技能知识库#xff0c;50个领域一键直达关闭bellman ford 算法 2013-05-25 15:36 11148人阅读 评论(0) 收藏 举报分类#xff1a;ACM#xff08;11评论得书啦 Get IT技能知识库50个领域一键直达 关闭 bellman ford 算法 2013-05-25 15:36 11148人阅读 评论(0) 收藏 举报 分类 ACM11 [cpp] view plaincopy span stylefont-family: Arial, Helvetica, sans-serif;span styleborder-bottom-width:1px; border-bottom-style:dashed; border-bottom-color:rgb(201,201,201)a hrefhttp://www.wutianqi.com/?p1890 target_blank stylebackground-color:transparent; border-width:0px 0px 1px; border-bottom-style:dashed; border-bottom-color:rgb(201,201,201); margin:0px; padding:0px; vertical-align:baseline; color:rgb(0,102,204); text-decoration:none; outline:noneDijkstra算法/a/span/spana hrefhttp://wutianqi-blog.b0.upaiyun.com/2011/01/2.png stylefont-family: Arial, Helvetica, sans-serif; background-color: transparent; border-width: 0px 0px 1px; border-bottom-style: dashed; border-bottom-color: rgb(201, 201, 201); margin: 0px; padding: 0px; vertical-align: baseline; color: rgb(0, 102, 204); text-decoration: none; outline: none;/aa hrefhttp://wutianqi-blog.b0.upaiyun.com/2011/01/4.png stylefont-family: Arial, Helvetica, sans-serif; background-color: transparent; border-width: 0px 0px 1px; border-bottom-style: dashed; border-bottom-color: rgb(201, 201, 201); margin: 0px; padding: 0px; vertical-align: baseline; color: rgb(0, 102, 204); text-decoration: none; outline: none;/aa hrefhttp://wutianqi-blog.b0.upaiyun.com/2011/01/bellman_ford.jpg stylefont-family: Arial, Helvetica, sans-serif; background-color: transparent; border-width: 0px 0px 1px; border-bottom-style: dashed; border-bottom-color: rgb(201, 201, 201); margin: 0px; padding: 0px; vertical-align: baseline; color: rgb(0, 102, 204); text-decoration: none; outline: none;/aspan stylefont-family: Arial, Helvetica, sans-serif;是处理单源最短路径的有效算法但它局限于边的权值非负的情况若图中出现权值为负的边Dijkstra算法就会失效求出的最短路径就可能是错的。这时候就需要使用其他的算法来求解最短路径/spana hrefhttp://www.wutianqi.com/?p1912 target_blank stylefont-family: Arial, Helvetica, sans-serif; background-color: transparent; border-width: 0px 0px 1px; border-bottom-style: dashed; border-bottom-color: rgb(201, 201, 201); margin: 0px; padding: 0px; vertical-align: baseline; color: rgb(0, 102, 204); text-decoration: none; outline: none;Bellman-Ford算法/aspan stylefont-family: Arial, Helvetica, sans-serif;就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼Richard Bellman, 动态规划的提出者和小莱斯特•福特Lester Ford发明。Bellman-Ford算法的流程如下/span 给定图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). 首先介绍一下松弛计算。如下图 松弛计算之前点B的值是8但是点A的值加上边上的权重2得到5比点B的值8小所以点B的值减小为5。这个过程的意义是找到了一条通向B点更短的路线且该路线是先经过点A然后通过权重为2的边到达点B。 当然如果出现一下情况 则不会修改点B的值因为346。 BellmanFord算法可以大致分为三个部分 第一初始化所有点。每一个点保存一个值表示从原点到达这个点的距离将原点的值设为0其它的点的值设为无穷大表示不可达。 第二进行循环循环下标为从1到n1n等于图中点的个数。在循环内部遍历所有的边进行松弛计算。 第三遍历途中所有的边edgeuv判断是否存在这样情况 dv d (u) w(u,v) 则返回false表示途中存在从源点可达的权为负的回路。 之所以需要第三部分的原因是因为如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。 考虑如下的图 经过第一次遍历后点B的值变为5点C的值变为8这时注意权重为10的边这条边的存在导致点A的值变为2。8 102 第二次遍历后点B的值变为3点C变为6点A变为4。正是因为有一条负边在回路中导致每次遍历后各个点的值不断变小。 在回过来看一下bellmanford算法的第三部分遍历所有边检查是否存在dv d (u) w(u,v)。因为第二部分循环的次数是定长的所以如果存在无法收敛的情况则肯定能够在第三部分中检查出来。比如 此时点A的值为2点B的值为5边AB的权重为55 -2 5. 检查出来这条边没有收敛。 所以BellmanFord算法可以解决图中有权为负数的边的单源最短路径问。 个人感觉算法导论讲解很不错把这一章贴出来和大家分享: 24.1 The Bellman-Ford algorithm The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G (V, E) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights. The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source. BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i ← 1 to |V[G]| - 1
3 do for each edge (u, v) ∈ E[G]
4 do RELAX(u, v, w)
5 for each edge (u, v) ∈ E[G]
6 do if d[v] d[u] w(u, v)
7 then return FALSE
8 return TRUE Figure 24.4 shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the d and π values of all vertices in line 1, the algorithm makes |V| – 1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We’ll see a little later why this check works.) 单击图片可以放大 Figure 24.4: The execution of the Bellman-Ford algorithm. The source is vertex s. The d values are shown within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then π[v] u. In this particular example, each pass relaxes the edges in the order (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The d and π values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example. The Bellman-Ford algorithm runs in time O(V E), since the initialization in line 1 takes Θ(V) time, each of the |V| – 1 passes over the edges in lines 2-4 takes Θ(E) time, and the for loop of lines 5-7 takes O(E) time. 以下是Bellman-Ford代码: [cpp] view plaincopy #include iostream using namespace std; const int maxnum 100; const int maxint 99999; // 边 typedef struct Edge{ int u, v; // 起点重点 int weight; // 边的权值 }Edge; Edge edge[maxnum]; // 保存边的值 int dist[maxnum]; // 结点到源点最小距离 int nodenum, edgenum, source; // 结点数边数源点 // 初始化图 void init() { // 输入结点数边数源点 cin nodenum edgenum source; for(int i1; inodenum; i) dist[i] maxint; dist[source] 0; for(int i1; iedgenum; i) { cin edge[i].u edge[i].v edge[i].weight; if(edge[i].u source) //注意这里设置初始情况 dist[edge[i].v] edge[i].weight; } } // 松弛计算 void relax(int u, int v, int weight) { if(dist[v] dist[u] weight) dist[v] dist[u] weight; } bool Bellman_Ford() { for(int i1; inodenum-1; i) for(int j1; jedgenum; j) relax(edge[j].u, edge[j].v, edge[j].weight); bool flag 1; // 判断是否有负环路 for(int i1; iedgenum; i) if(dist[edge[i].v] dist[edge[i].u] edge[i].weight) { flag 0; break; } return flag; } int main() { //freopen(input3.txt, r, stdin); init(); if(Bellman_Ford()) for(int i 1 ;i nodenum; i) cout dist[i] endl; return 0; } 补充: 考虑为什么要循环V-1次 答因为最短路径肯定是个简单路径不可能包含回路的 如果包含回路且回路的权值和为正的那么去掉这个回路可以得到更短的路径 如果回路的权值是负的那么肯定没有解了 图有n个点又不能有回路 所以最短路径最多n-1边 又因为每次循环至少relax一边 所以最多n-1次就行了 顶3 踩0 上一篇HDOJ---2036 过山车[匈牙利算法] 下一篇ACM进阶指南 我的同类文章 ACM11 •Uva 10891 sum 游戏 及其变型 动态规划2013-05-31阅读440•二分图匹配算法总结2013-05-25阅读839•求最大权二分匹配的KM算法2013-05-25阅读353•ACM进阶指南2013-05-25阅读629•匈牙利算法 求解 完美的牛栏2013-05-24阅读1106 •欧拉回路2013-05-28阅读347•二分图带权匹配 KM算法与费用流模型建立2013-05-25阅读650•著名的北邮ACM推荐50题2013-05-25阅读1702•HDOJ---2036 过山车[匈牙利算法]2013-05-24阅读601•hdu 1466计算直线的交点数2013-05-03阅读579 更多文章 参考知识库 算法与数据结构知识库 10401关注|2281收录 猜你在找 《C语言/C学习指南》加密解密篇安全相关算法 C语言系列之 递归算法示例与 Windows 趣味小项目 C语言系列之 字符串相关算法 C语言系列之 字符串压缩算法与结构体初探 模板匹配的字符识别(OCR)算法原理 图最短路径Bellman-Ford算法 BellmanFord算法实现解决存在负边情况下单源最短路径问题 最短路模板Dijkstra Dijkstra算法堆优化 bellman_ford 单源最短路SPFA 最短路径算法Bellman-Ford贝尔曼 poj Wormholes 最短路 spfa Bellman-Ford 算法 邻接表实现 查看评论 暂无评论 发表评论 用 户 名 hang__xiu2016acm 评论内容 * 以上用户言论只代表其个人观点不代表CSDN网站的观点或立场 核心技术类目 全部主题 Hadoop AWS 移动游戏 Java Android iOS Swift 智能硬件 Docker OpenStack VPN Spark ERP IE10Eclipse CRM JavaScript 数据库 Ubuntu NFC WAP jQuery BI HTML5 Spring Apache .NET API HTML SDK IISFedora XML LBS Unity Splashtop UML components Windows Mobile Rails QEMU KDE Cassandra CloudStack FTCcoremail OPhone CouchBase 云计算 iOS6 Rackspace Web App SpringSide Maemo Compuware 大数据 aptech PerlTornado Ruby Hibernate ThinkPHP HBase Pure Solr Angular Cloud Foundry Redis Scala Django Bootstrap 个人资料 Flyer_ 访问75445次积分1071等级 排名千里之外 原创24篇转载47篇译文0篇评论10条 文章搜索 文章分类 unix环境高级编程(18)unix网络编程(4)tcp/ip(4)unix/linux(10)ACM(12)笔试(13)面试(8)PAT(4)30天自制操作系统(1)前端(4)HTMLCSS(3)ML(7) 文章存档 2016年10月(1) 2016年08月(1) 2016年07月(6) 2015年07月(3) 2015年03月(1) 展开 阅读排行 bellman ford 算法(11142)网络爬虫c实现(9636)2014阿里巴巴9月14北京校园招聘笔试及参考答案(3983)两道操作系统题目---多道程序(3511)TCP/IP网络编程之四书五经(2704)2012九月十月腾讯网易游戏百度最新校园招聘笔试题(2619)Linux进程地址空间与虚拟内存(2337)PAT 1010. 一元多项式求导 (25)(2186)PAT 1009. 说反话 (20)(2011)腾讯后台开发面试题(1764) 评论排行 2014阿里巴巴9月14北京校园招聘笔试及参考答案(3)网络爬虫c实现(2)进程与线程的一个简单解释(2)两道操作系统题目---多道程序(1)LINUX/UNIX 文件状态标志的 与或非 操作(1)编程之美_单链表面试题_结合3.4_3.6(1)2014找工作总结-机会往往留给有准备的人(1)著名的北邮ACM推荐50题(0)ACM进阶指南(0)匈牙利算法 求解 完美的牛栏(0) 推荐文章 * RxJava详解由浅入深* 倍升工作效率的小策略* Android热修复框架AndFix原理解析及使用* “区块链”究竟是什么鬼* 架构设计系统存储-MySQL主从方案业务连接透明化中 最新评论 两道操作系统题目---多道程序 Daringoo: 第二题腾讯给的标准答案是A。在csdn上有自动的测试我看到了显示的答案。但是不知怎么得来的。 ssd8ex1 Tiger_Humour: 楼主你好请问18到25行代码里的;这一段代码是如何确定uri.indexOf(/,8)1的。... 网络爬虫c实现 Echo_Wei1991: 正在写这个的大作业谢谢啦~太赞 进程与线程的一个简单解释 qwe8642511: 很好但是为什么那个锁上在了门外面。。。。。。出不来了~ 2014阿里巴巴9月14北京校园招聘笔试及参考答案 weidahou227: xiaor186:大哥你能好好算算在评论吗字母有重复的 2014阿里巴巴9月14北京校园招聘笔试及参考答案 xiaor186: 哎哥啊看来这参考答案也真的是只能是参考下而已。第一个的答案用脚趾数都不可能是D吧应该是A 编程之美_单链表面试题_结合3.4_3.6 岁月小龙: 没有实现代码啊 网络爬虫c实现 岁月小龙: xialai慢慢看 进程与线程的一个简单解释 岁月小龙: 这个图文并茂真是太好了 2014找工作总结-机会往往留给有准备的人 Deebug: 谢谢博主的建议。1 链接 Hackbuteer1 结构之法 算法之道 公司简介|招贤纳士|广告服务|联系方式|版权声明|法律顾问|问题报告|合作伙伴|论坛反馈 网站客服杂志客服微博客服webmastercsdn.net400-600-2320|北京创新乐知信息技术有限公司 版权所有|江苏知之为计算机有限公司|江苏乐知网络技术有限公司 京 ICP 证 09002463 号|Copyright © 1999-2016, CSDN.NET, All Rights Reserved
