Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。
这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(RichardBellman,动态规划的提出者)和小莱斯特•福特(LesterFord)发明。
适用条件&范围:
单源最短路径(从源点s到其它所有顶点v);
有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
边权可正可负(如有负权回路输出错误提示);
差分约束系统;
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).
Bellman-Ford算法可以大致分为三个部分
第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
第三,遍历途中所有的边(edge(u,v)),判断是否存在这样情况:
d(v)>d(u)+w(u,v)
则返回false,表示途中存在从源点可达的权为负的回路。
之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。
测试代码如下:(下面为有向图的Bellman-Ford算法。。。。。)
测试数据:
4 6 1
1 2 20
1 3 5
4 1 -200
2 4 4
4 2 4
3 4 2
和:
4 6 1
1 2 2
1 3 5
4 1 10
2 4 4
4 2 4
3 4 2
分享到:
相关推荐
bellman-ford算法的C++实现,邻接表
Bellman-Ford算法与差分约束系统
Java实现的Dijkstra算法和Bellman-ford算法代码,带UI界面,已封装的可执行jar文件,以及源代码。
分步介绍了bellman-ford算法的详细步骤和分析方法,最后给出了例题进行了说明
NULL 博文链接:https://128kj.iteye.com/blog/1715073
受求解最短路径问题的Bellman-Ford算法的启发,我们证明了所提出的路径公式可以被广义Bellman-Ford算法有效地求解。为了进一步提高路径表示的能力,我们提出了神经BellmanFord网络(NBFNet),这是一个通用的图神经...
基于Bellman-Ford最短路径算法的演示程序 提供源代码
Bellman-Ford算法是一种用于计算图中单源最短路径的算法,可以处理带有负权边的图。使用Python实现了这个算法。 Bellman-Ford算法是一种用于计算图中单源最短路径的算法,它可以处理带有负权边的图。以下是Bellman-...
最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(CC++),希望对你能有所帮助!
C#,图论与图算法,有向图单源最短路径的贝尔曼·福特(Bellman Ford)算法与源代码 贝尔曼·福特(Bellman Ford)算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)的算法。该算法...
Bellman-ford算法.ppt
Bellman-Ford算法.docx
经典算法书籍《算法导论》之图算法章节中Bellman-ford算法的C++版。
Bellman-Ford算法(单源最短路径) 矩阵是在main函数里输入的 可以处理带负权的图
图论- 最短路- Bellman-Ford 算法与 SPFA.rar
蓝桥杯CJ2-11-图论最短路径问题 Bellman-Ford算法+SPFA.pdf
Bellman-Ford算法性能可移植的GPU并行优化.pdf
c代码-最短路径Bellman-Ford算法
bellman-Ford算法的具体实现,用c++的语法实现,简单易懂。
bellman-ford算法bellman-ford算法bellman-ford算法bellman-ford算法bellman-ford算法bellman-ford算法