本文主要是介绍算法导论——24.1 BellmanFord算法java实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
介绍
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. 差分约束系统;
算法描述
1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] ——>+∞, d[s]——>0;
2.迭代求解:反复对边集E中的每条边进行 松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)
3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在 d[v]中。
这篇关于算法导论——24.1 BellmanFord算法java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!