Bellman - ford算法是求含负权图的单源来自最短路径的一种算法，360百科效率较低，代码难度较小。其原理为连续溶山跳门序进行松弛，在每间是示振陆语果己铁次松弛时把每条边都更新一下，向消围华独明走对若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

• 中文名 贝尔曼-福特算法
• 外文名 Bellman - Ford algorithm
• 算法类别 求含负权图的单源最短路径算法
• 缺点 效率很低  O(NM)
• 优点 有较高实用性，适用于负权图。

介绍

　　Dijkstra算法无法判断含负权边的图的最短路。如果来自遇到负权，在没有负权回路(回360百科路的权值和为负，即便有负权的边)存在时，也可以采用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.差分约束系统;

算法描述

　　1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] -->+∞, d[s]-->0;

　氧府口哥下负纪月当随就　2.迭代求解:反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离来自估计值逐步逼近其最短距离;(运行|v|-1次)

　　3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回fals360百科e，表明问题无解;否则算法本返回true，并且从源点可达的顶查案点v的最短距离保存在 d[洋千检v]中。

描述性证明

　　首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路呀至周销船命次，因此它最多包含|v|-1条边。

　　其次，从源点s可达的站所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按每个点实际的最短路径[虽然我们还不知道，但它一定存在]的层次，逐层生成这棵最短路径树的过程。

　　注意，每一次遍历，都可以从前一次遍历的基础上，找到此千己逐注应宗次遍历的部分点的单源最短路径。如:这是第i次遍历，那么，通过数学归纳法，若前面单源最短路径层次为1~(i-1)的点全部已经得到，而单源最短路径层次为i的点，必定可由单源最短路径层次执因定为i-1的点集得到，从而在下一次遍历中充当前一次的点集，如此往复迭代，[v]-1次后，若无负权回路，则我草们已经达到了所需的目的--得到每个点的单源最短路时诉笔赵径。[注意:这棵树的每一次更新，可以将其中的某一个子树接到另一个点下]

　　反之，可证，若存在负权回路，第[v]次遍历一定存在更新，因为负权回路的环中，必定存在一个"断点"，可用数学手段证明。

　　最后，我们在第[v]次更新中若没有新的松弛，则输角出结果，若依然存在松弛，则输出'CAN'T'表示无解。同时，我们还可以通过"断点"找到负权回路。

伪代码

　　时间复杂度

　　算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。

参考代祖希织赶宁顾地的学械码

　　PASCAL

　　{单源最短路径的Bellman-ford算法

　　执行v-1次，每次对每条边进行松弛操作

　　如有负权回路则盾孙西附位烈输出"Error!!"}

　　Matlab

　　C++

引申内容

　　SP晶青扩七各表FA算法

　　SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列优化，减少了不必要的冗余计算。

算法流程

　　算法风大致流程是用一个队列来进行章错现县维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛孔，若某个相邻的点松降游副与践和县安升极文弛成功，则将其入队。 直到队列为空时算法结束。

算法的优化

　　分析 Bellman-Ford算法，不难看出，外层循环(迭代次数)|v|-1实际上取得是上限。由上面对算法正确性的证明可知，需要的迭代遍数等于最短路径树的高度。如果不存在负权回路，平均情况下的最短路径树的高度应该远远小于 |v|-1，在此情况下，多余最短路径树高的迭代遍数就是时间上的浪费，由此，可以依次来实施优化。

　　从细节上分析，如果在某一遍迭代中，算法描述中第7行的松弛操作未执行，说明该遍迭代所有的边都没有被松弛。可以证明(怎么证明?):至此后，边集中所有的边都不需要再被松弛，从而可以提前结束迭代过程。这样，优化的措施就非常简单了。

　　设定一个布尔型标志变量 relaxed，初值为false。在内层循环中，仅当有边被成功松弛时，将 relaxed 设置为true。如果没有边被松弛，则提前结束外层循环。这一改进可以极大的减少外层循环的迭代次数。优化后的 bellman-ford函数如下。

　　这样看似平凡的优化，会有怎样的效果呢?有研究表明，对于随机生成数据的平均情况，时间复杂度的估算公式为

　　1.13|E| if |E|<|V|

　　0.95*|E|*lg|V| if |E|>|V|

　　优化后的算法在处理有负权回路的测试数据时，由于每次都会有边被松弛，所以relaxed每次都会被置为true，因而不可能提前终止外层循环。这对应了最坏情况，其时间复杂度仍旧为O(VE)。

　　优化后的算法的时间复杂度已经和用二叉堆优化的Dijkstra算法相近了，而编码的复杂程度远比后者低。加之Bellman-Ford算法能处理各种边值权情况下的最短路径问题，因而还是非常优秀的。