详解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算法原理及实现的文章就介绍到这了,更多相关Java Bellman-Ford算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java实现Dijkstra算法的示例代码

    Java实现Dijkstra算法的示例代码

    目录 一 问题描述 二 实现 三 测试 一 问题描述 小明为位置1,求他到其他各顶点的距离. 二 实现 package graph.dijkstra; import java.util.Scanner; import java.util.Stack; public class Dijkstra { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int

  • C++图论之Bellman-Ford算法和SPFA算法的实现

    C++图论之Bellman-Ford算法和SPFA算法的实现

    目录 Bellman-Ford算法 例题:AcWing 853. 有边数限制的最短路 算法步骤 代码实现 SPFA算法 代码实现 给定一张有向图,若对于图中的某一条边(x,y,z),有dist[y]≤dist[x]+z成立,则称该边满足三角形不等式.如果所有边都满足三角形不等式,则dist数组就是所求的最短路. Bellman-Ford算法 (x,y,z)表示的是一条从 x 出发, 到达 y ,长度为 z 的有向边. 首先介绍基于迭代的Bellman-Ford算法,它的流程如下: 1.扫描所有边

  • c++ Bellman-Ford算法的具体实现

    c++ Bellman-Ford算法的具体实现

    Bellman-Ford算法用于解决有边数限制的最短路问题,且可以应对有负边权的图 其时间复杂度为O(nm),效率较低 代码实现: #include<iostream> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f using namespace std; const int N=1e4+10; const int M=510; int m,n,k,dis[M],backup[M]; //m条边

  • C++计算任意权值的单源最短路径（Bellman-Ford）

    本文实例为大家分享了C++计算任意权值单源最短路径的具体代码,供大家参考,具体内容如下 一.有Dijkstra算法求最短路径了,为什么还要用Bellman-Ford算法 Dijkstra算法不适合用于带有负权值的有向图. 如下图: 用Dijkstra算法求顶点0到各个顶点的最短路径: (1)首先,把顶点0添加到已访问顶点集合S中,选取权值最小的邻边<0, 2>,权值为5 记录顶点2的最短路径为:dist[2]=5, path[2]=0,把顶点2添加到集合S中. 顶点2,没有邻边(从顶点2出发,

  • Java实现Floyd算法的示例代码

    Java实现Floyd算法的示例代码

    目录 一 问题描述 二 代码 三 实现 一 问题描述 求节点0到节点2的最短路径. 二 代码 package graph.floyd; import java.util.Scanner; public class Floyd { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int dist[][] = new int[MaxVnum][MaxVnum

  • 详解Java实现分治算法

    详解Java实现分治算法

    目录 一.前言 二.分治算法介绍 三.分治算法经典问题 3.1.二分搜索 3.2.快速排序 3.3.归并排序(逆序数) 3.4.最大子序列和 3.5.最近点对 四.结语 一.前言 在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱.但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了 当然如果你觉得各个部分

  • 详解Java中KMP算法的图解与实现

    详解Java中KMP算法的图解与实现

    目录 图解 代码实现 图解 kmp算法跟之前讲的bm算法思想有一定的相似性.之前提到过,bm算法中有个好后缀的概念,而在kmp中有个好前缀的概念,什么是好前缀,我们先来看下面这个例子. 观察上面这个例子,已经匹配的abcde称为好前缀,a与之后的bcde都不匹配,所以没有必要再比一次,直接滑动到e之后即可. 那如果好前缀中有互相匹配的字符呢? 观察上面这个例子,这个时候如果我们直接滑到好前缀之后,则会过度滑动,错失匹配子串.那我们如何根据好前缀来进行合理滑动? 其实就是看当前的好前缀的前缀和后缀

  • 详解Java信号量Semaphore的原理及使用

    详解Java信号量Semaphore的原理及使用

    目录 1.Semaphore的概述 2.Semaphore的原理 2.1 基本结构 2.2 可中断获取信号量 2.3 不可中断获取信号量 2.4 超时可中断获取信号量 2.5 尝试获取信号量 2.6 释放信号量 3.Semaphore的使用 4.Semaphore的总结 1.Semaphore的概述 public class Semaphore extends Object implements Serializable Semaphore来自于JDK1.5的JUC包,直译过来就是信号量,被作为

  • 详解Java Synchronized的实现原理

    详解Java Synchronized的实现原理

    目录 Synchronized Synchronized的使用方式 Synchronized的底层实现 1.Java对象头 2.Monitor 3.线程状态流转在Monitor上体现 Synchronized 的锁升级 谈到多线程就不得不谈到Synchronized,重要性不言而喻,今天主要谈谈Synchronized的实现原理. Synchronized synchronized关键字解决的是多个线程之间访问资源的同步性,synchronized 翻译为中文的意思是同步,也称之为”同步锁“.

  • 详解java数据结构与算法之双链表设计与实现

    详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • 详解vue的diff算法原理

    详解vue的diff算法原理

    我的目标是写一个非常详细的关于diff的干货,所以本文有点长.也会用到大量的图片以及代码举例,目的让看这篇文章的朋友一定弄明白diff的边边角角. 先来了解几个点... 1. 当数据发生变化时,vue是怎么更新节点的? 要知道渲染真实DOM的开销是很大的,比如有时候我们修改了某个数据,如果直接渲染到真实dom上会引起整个dom树的重绘和重排,有没有可能我们只更新我们修改的那一小块dom而不要更新整个dom呢?diff算法能够帮助我们. 我们先根据真实DOM生成一颗 virtual DOM ,当

  • 详解Java数据结构和算法（有序数组和二分查找）

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • 详解Java中AC自动机的原理与实现

    详解Java中AC自动机的原理与实现

    目录 简介 工作过程 数据结构 初始化 构建字典树 构建失败指针 匹配 执行结果 简介 AC自动机是一个多模式匹配算法,在模式匹配领域被广泛应用,举一个经典的例子,违禁词查找并替换为***.AC自动机其实是Trie树和KMP 算法的结合,首先将多模式串建立一个Tire树,然后结合KMP算法前缀与后缀匹配可以减少不必要比较的思想达到高效找到字符串中出现的匹配串. 如果不知道什么是Tire树,可以先查看:详解Java中字典树(Trie树)的图解与实现 如果不知道KMP算法,可以先查看:详解Java中

  • 详解Java Bellman-Ford算法原理及实现

    详解Java Bellman-Ford算法原理及实现

    目录 一 点睛 二 算法步骤 三 算法实现 四 测试 一 点睛 如果遇到负权边,则在没有负环(回路的权值之和为负)存在时,可以采用 Bellman-Ford 算法求解最短路径.该算法的优点是变的权值可以是负数.实现简单,缺点是时间复杂度过高.但是该算法可以进行若干种优化,以提高效率. Bellman-Ford 算法与 Dijkstra 算法类似,都是以松弛操作作为基础.Dijkstra 算法以贪心法选取未被处理的具有最小权值的节点,然后对其进行松弛操作:而 Bellman-Ford 算法对所有边

  • 基数排序算法的原理与实现详解(Java/Go/Python/JS/C)

    目录 说明 实现过程 示意图 性能分析 代码 Java Python Go JS TS C C++ 链接 说明 基数排序(RadixSort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数.基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(Tabulation Machine)上的 基数排序的方式可以采用LSD(Least significant di

随机推荐