您好,登录后才能下订单哦!
本篇内容介绍了“Java Bellman-Ford算法原理及实现方法”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
如果遇到负权边,则在没有负环(回路的权值之和为负)存在时,可以采用 Bellman-Ford 算法求解最短路径。该算法的优点是变的权值可以是负数、实现简单,缺点是时间复杂度过高。但是该算法可以进行若干种优化,以提高效率。
Bellman-Ford 算法与 Dijkstra 算法类似,都是以松弛操作作为基础。Dijkstra 算法以贪心法选取未被处理的具有最小权值的节点,然后对其进行松弛操作;而 Bellman-Ford 算法对所有边都进行松弛操作,共 n-1 次。因为负环可以无限制地减少最短路径长度,所以吐过发现第 n 次操作仍然可松弛,则一定存在负环。Bellman-Ford 算法最长运行时间为O(nm),其中 n 和 m 分别是节点数和边数。
1 数据结构
因为需要利用边进行松弛,因此采用边集数组存储。每条边都有三个域:两个端点a和b,以及边权w
2 松弛操作
对所有的边 j(a,b,w),如果 dis[e[j]b]>dis[e[j].a]+e[j].w,则松弛,另 dis[e[j]b]=dis[e[j].a]+e[j].w。其中,dis[v] 表示从源点到节点 v 的最短路径长度。
3 重复松弛操作 n-1 次
4 负环判断
再执行一次松弛操作,如果仍然可以松弛,则说明右负环。
package graph.bellmanford; import java.util.Scanner; public class BellmanFord { static node e[] = new node[210]; static int dis[] = new int[110]; static int n; static int m; static int cnt = 0; static { for (int i = 0; i < e.length; i++) { e[i] = new node(); } } static void add(int a, int b, int w) { e[cnt].a = a; e[cnt].b = b; e[cnt++].w = w; } static boolean bellman_ford(int u) { // 求源点 u 到其它顶点的最短路径长度,判负环 for (int i = 0; i < dis.length; i++) { dis[i] = 0x3f; } dis[u] = 0; for (int i = 1; i < n; i++) { // 执行 n-1 次 boolean flag = false; for (int j = 0; j < m; j++) // 边数 m 或 cnt if (dis[e[j].b] > dis[e[j].a] + e[j].w) { dis[e[j].b] = dis[e[j].a] + e[j].w; flag = true; } if (!flag) return false; } for (int j = 0; j < m; j++) // 再执行 1 次,还能松弛说明有环 if (dis[e[j].b] > dis[e[j].a] + e[j].w) return true; return false; } static void print() { // 输出源点到其它节点的最短距离 System.out.println("最短距离:"); for (int i = 1; i <= n; i++) System.out.print(dis[i] + " "); System.out.println(); } public static void main(String[] args) { int a, b, w; Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 0; i < m; i++) { a = scanner.nextInt(); b = scanner.nextInt(); w = scanner.nextInt(); add(a, b, w); } if (bellman_ford(1)) // 判断负环 System.out.println("有负环!"); else print(); } } class node { int a; int b; int w; }
1 没有负环的测试
2 有负环的测试
“Java Bellman-Ford算法原理及实现方法”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。