Bellman-Ford算法

深碍√TFBOYSˉ_ 2022-04-11 07:19 140阅读 0赞

# 概述： #

Bellman - ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。其原理为持续地进行松弛（原文是这么写的，为什么要叫松弛，争议很大），在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。Bellman - ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间去做没有必要的松弛，而SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。

# 介绍 #

Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权，在没有负权回路存在时（负权回路的含义是，回路的权值和为负。）即便有负权的边，也可以采用Bellman - Ford算法正确求出最短路径。  
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=(V,E), 其源点为s，加权函数 w是 边集 E 的映射。对图G运行Bellman - Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d\[v\]。

# 适用条件 #

1.单源最短路径(从源点s到其它所有顶点v);  
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);  
3.边权可正可负(如有负权回路输出错误提示);  
4.差分约束系统;

# 思想： #

## Bellman-Ford 算法描述： ##

1.创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；

2.计算最短路径，执行 V - 1 次遍历；

3.对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；

4.检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；

# 注意： #

上面的最后一步用于检测闭环的存在

# 步骤： #

![这里写图片描述][20160902142905650]

# 检测步骤： #

![这里写图片描述][20160902142924744]

# 实例： #

![这里写图片描述][20160902143539597]  
参考：  
[http://www.voidcn.com/blog/u010087886/article/p-4529113.html][http_www.voidcn.com_blog_u010087886_article_p-4529113.html]  
[http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn][http_baike.baidu.com_view_1712262.htm_fromtitle_Dijkstra_E7_AE_97_E6_B3_95_fromid_215612_type_syn]  
[http://www.cnblogs.com/gaochundong/p/bellman\_ford\_algorithm.html][http_www.cnblogs.com_gaochundong_p_bellman_ford_algorithm.html]

# #

[20160902142905650]: /images/20220411/10471df7610f44d1aa74ef904fabf08d.png
[20160902142924744]: /images/20220411/9df930b580694b6bbc56ec87325ec5ba.png
[20160902143539597]: /images/20220411/30de222954034500af9fe037ef19b12f.png
[http_www.voidcn.com_blog_u010087886_article_p-4529113.html]: http://www.voidcn.com/blog/u010087886/article/p-4529113.html
[http_baike.baidu.com_view_1712262.htm_fromtitle_Dijkstra_E7_AE_97_E6_B3_95_fromid_215612_type_syn]: http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn
[http_www.cnblogs.com_gaochundong_p_bellman_ford_algorithm.html]: http://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html