最短路径算法:Bellman-Ford算法
引言
在图论中,Bellman-Ford算法是一种用于计算单源最短路径的算法。与Dijkstra算法不同,Bellman-Ford算法可以处理带有负权边的图,并且可以检测图中是否存在负权环。本文将详细介绍Bellman-Ford算法的定义、步骤及其实现。
Bellman-Ford算法
定义
Bellman-Ford算法是一种用于计算从源顶点到图中所有其他顶点的最短路径的算法。该算法可以处理带有负权边的图,并且可以检测是否存在负权环。
算法步骤
- 初始化:设定源顶点的距离为0,其余顶点的距离为正无穷大。
- 松弛操作:对所有边进行(V-1)次松弛操作,其中(V)是顶点的数量。对于每条边(u, v),如果
dist[u] + weight < dist[v],则更新dist[v] = dist[u] + weight。 - 检查负权环:对所有边进行一次检查,如果发现仍然可以进行松弛操作,则说明图中存在负权环。
示例
假设我们有一个带权有向图,顶点集合为 ({A, B, C, D, E}),边和权重集合为 ({(A, B, -1), (A, C, 4), (B, C, 3), (B, D, 2), (B, E, 2), (D, B, 1), (D, C, 5), (E, D, -3)})。
Bellman-Ford算法图解
步骤1:初始化
将源顶点A的距离设为0,其余顶点的距离设为正无穷大。
顶点: A B C D E
距离: 0 ∞ ∞ ∞ ∞
步骤2:第一次松弛操作
对每条边进行松弛操作:
- 对于边 (A, B, -1):更新 B 的距离为 -1。
- 对于边 (A, C, 4):更新 C 的距离为 4。
- 对于边 (B, C, 3):更新 C 的距离为 2。
- 对于边 (B, D, 2):更新 D 的距离为 1。
- 对于边 (B, E, 2):更新 E 的距离为 1。
- 对于边 (D, B, 1):不更新 B 的距离。
- 对于边 (D, C, 5):不更新 C 的距离。
- 对于边 (E, D, -3):更新 D 的距离为 -2。
顶点: A B C D E
距离: 0 -1 2 -2 1
步骤3:第二次松弛操作
对每条边再次进行松弛操作:
- 对于边 (A, B, -1):不更新 B 的距离。
- 对于边 (A, C, 4):不更新 C 的距离。
- 对于边 (B, C, 3):不更新 C 的距离。
- 对于边 (B, D, 2):不更新 D 的距离。
- 对于边 (B, E, 2):不更新 E 的距离。
- 对于边 (D, B, 1):不更新 B 的距离。
- 对于边 (D, C, 5):不更新 C 的距离。
- 对于边 (E, D, -3):不更新 D 的距离。
顶点: A B C D E
距离: 0 -1 2 -2 1
步骤4:检查负权环
对每条边进行一次检查,如果发现仍然可以进行松弛操作,则说明图中存在负权环。在此示例中,没有发现负权环。
Bellman-Ford算法实现
下面是用Java实现Bellman-Ford算法的代码示例:
import java.util.Arrays;public class BellmanFordAlgorithm {private int vertices; // 顶点数量private int[][] edges; // 边数组,包含边的起点、终点和权重private int edgeCount; // 边数量public BellmanFordAlgorithm(int vertices, int edgeCount) {this.vertices = vertices;this.edgeCount = edgeCount;edges = new int[edgeCount][3];}// 添加边public void addEdge(int edgeIndex, int src, int dest, int weight) {edges[edgeIndex][0] = src;edges[edgeIndex][1] = dest;edges[edgeIndex][2] = weight;}// 计算从源顶点到所有顶点的最短路径public void bellmanFord(int src) {int[] dist = new int[vertices]; // 最短距离数组Arrays.fill(dist, Integer.MAX_VALUE);dist[src] = 0;// 对所有边进行 V-1 次松弛操作for (int i = 1; i < vertices; i++) {for (int j = 0; j < edgeCount; j++) {int u = edges[j][0];int v = edges[j][1];int weight = edges[j][2];if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;}}}// 检查是否存在负权环for (int j = 0; j < edgeCount; j++) {int u = edges[j][0];int v = edges[j][1];int weight = edges[j][2];if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {System.out.println("图中存在负权环");return;}}printSolution(dist);}// 打印最短路径private void printSolution(int[] dist) {System.out.println("顶点\t距离源顶点");for (int i = 0; i < vertices; i++) {System.out.println(i + "\t\t" + dist[i]);}}public static void main(String[] args) {int vertices = 5;int edgeCount = 8;BellmanFordAlgorithm graph = new BellmanFordAlgorithm(vertices, edgeCount);graph.addEdge(0, 0, 1, -1);graph.addEdge(1, 0, 2, 4);graph.addEdge(2, 1, 2, 3);graph.addEdge(3, 1, 3, 2);graph.addEdge(4, 1, 4, 2);graph.addEdge(5, 3, 1, 1);graph.addEdge(6, 3, 2, 5);graph.addEdge(7, 4, 3, -3);graph.bellmanFord(0); // 从顶点0开始计算最短路径}
}
代码注释
-
类和构造函数:
public class BellmanFordAlgorithm {private int vertices; // 顶点数量private int[][] edges; // 边数组,包含边的起点、终点和权重private int edgeCount; // 边数量public BellmanFordAlgorithm(int vertices, int edgeCount) {this.vertices = vertices;this.edgeCount = edgeCount;edges = new int[edgeCount][3];}BellmanFordAlgorithm类包含图的顶点数量和边数组,并有一个构造函数来初始化这些变量。 -
添加边:
public void addEdge(int edgeIndex, int src, int dest, int weight) {edges[edgeIndex][0] = src;edges[edgeIndex][1] = dest;edges[edgeIndex][2] = weight; }addEdge方法用于向图中添加边。 -
Bellman-Ford算法:
public void bellmanFord(int src) {int[] dist = new int[vertices]; // 最短距离数组Arrays.fill(dist, Integer.MAX_VALUE);dist[src] = 0;// 对所有边进行 V-1 次松弛操作for (int i = 1; i < vertices; i++) {for (int j = 0; j < edgeCount; j++) {int u = edges[j][0];int v = edges[j][1];int weight = edges[j][2];if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;}}}// 检查是否存在负权环for (int j = 0; j < edgeCount; j++) {int u = edges[j][0];int v = edges[j][1];int weight = edges[j][2];if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {System.out.println("图中存在负权环");return;}}printSolution(dist); }bellmanFord方法实现了Bellman-Ford算法,计算从源顶点到所有其他顶点的最短路径,并检测是否存在负权环。 -
打印最短路径:
private void printSolution(int[] dist) {System.out.println("顶点\t距离源顶点");for (int i = 0; i < vertices; i++) {System.out.println(i + "\t\t" + dist[i]);} }printSolution方法用于打印最短路径。
结论
通过上述讲解和实例代码,我们详细展示了Bellman-Ford算法的定义、步骤及其实现。Bellman-Ford算法是一种重要的最短路径算法,特别适用于带有负权边的图,并且可以检测负权环。希望这篇博客对您有所帮助!
如果您觉得这篇文章对您有帮助,请关注我的CSDN博客,点赞并收藏这篇文章,您的支持是我持续创作的动力!
关键内容总结:
- Bellman-Ford算法的定义
- Bellman-Ford算法的步骤
- Bellman-Ford算法的实现及其代码注释
推荐阅读:深入探索设计模式专栏,详细讲解各种设计模式的应用和优化。点击查看:深入探索设计模式。
特别推荐:设计模式实战专栏,深入解析设计模式的实际应用,提升您的编程技巧。点击查看:设计模式实战。
如有任何疑问或建议,欢迎在评论区留言讨论。谢谢阅读!
相关文章:
最短路径算法:Bellman-Ford算法
引言 在图论中,Bellman-Ford算法是一种用于计算单源最短路径的算法。与Dijkstra算法不同,Bellman-Ford算法可以处理带有负权边的图,并且可以检测图中是否存在负权环。本文将详细介绍Bellman-Ford算法的定义、步骤及其实现。 Bellman-Ford算…...
爬虫:xpath模块及昵图网实例
xpath模块 from lxml import etreestr1 """ <div><ul><li class"item-0"><a href"link1.html">first item</a></li><li class"item-1"><a href"link2.html">second…...
高级java每日一道面试题-2024年8月03日-web篇-forward和redirect有什么区别?
如果有遗漏,评论区告诉我进行补充 面试官: forward和redirect有什么区别? 我回答: 在Java Web开发中,forward和redirect是Servlet容器提供的两种用于页面跳转的技术。它们的主要区别在于客户端感知的方式、URL地址的变化、请求对象的共享等方面。下面详细介绍两…...
如何让你的网站拥有更好的体验
在HTML中,属性是用于提供关于HTML元素的额外信息。接下来我们将讲解13个可以让用户拥有更好体验的HTML属性。 Accept 属性 我们可以在<input>元素(仅适用于文件类型)中使用accept属性来指定服务器可以接受的文件类型。 <input ty…...
opencascade AIS_TypeFilter AIS_XRTrackedDevice源码学习
opencascade AIS_TypeFilter 前言 通过它们的类型选择交互对象。该过滤器会对本地上下文中的每个交互对象提出问题, 以确定它是否具有非空的所有者,并且如果是,则检查它是否是所需类型。 如果对象在每种情况下都返回 true,则保留…...
使用Spring AOP监控指定方法执行时间
文章目录 一、加入pom依赖二、切面类和注解三、执行方法 一、加入pom依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId></dependency>二、切面类和注解 import java.lang.…...
最新CSS3纵向菜单的实现
纵向菜单 通过下面例子,你会知道把列表转换成菜单的关键技术 a中的#是URL的占位符可以点击,真正用途中写实际URL <nav class"list1"><ul><li><a href"#">Alternative</a></li><li><…...
GooLeNet模型搭建
一、model import torch from torch import nn from torchsummary import summaryclass Inception(nn.Module):def __init__(self, in_channels, c1, c2 , c3 , c4):super(Inception, self).__init__()self.ReLU nn.ReLU()#路线1:1x1卷积self.p1_1 nn.Conv2d(in_channels i…...
使用ThreadLocal来存取单线程内的数据
一.什么是ThreadLocal? ThreadLocal,即线程本地变量。如果你创建了一个 ThreadLocal变量,那么访问这个变量的每个线程都会有这个变量的一个本地拷贝,多个线程操作这个变量的时候,实际是在操作自己本地内存里面的变量&…...
elasticsearch教程
1. 单点部署(rpm): #提前关闭firewalld,否则无法组建集群 #1. 下载ES rpm包 ]# https://www.elastic.co/cn/downloads #2. 安装es ]# rpm -ivh elasticsearch-7.17.5-x86_64.rpm #3. 调整内核参数(太低的话es会启动报错) echo "vm.max_map_count655360 fs.file-max 655…...
Arrays、Lambda表达式、Collection集合
1. Arrays 1.1 操作数组的工具类 方法名说明public static String toString(数组)把数组拼接成一个字符串public static int binarySearch(数组,查找的元素)二分查找法查找元素public static int[] copyOf(原数组,新数组长度)拷贝数组public static int[] copyOfRange(原数组…...
2024年前端趋势:全栈或许是不容错过的选择!
近年来,前端开发的技术不断推陈出新,2024年也不例外。在这个变化迅速的领域,全栈开发逐渐成为一股不容忽视的趋势。无论你是经验丰富的开发者,还是刚刚入门的新手,掌握全栈技术都能让你在竞争中脱颖而出。而在这个过程…...
MySQL 实战 45 讲(01-05)
本文为笔者学习林晓斌老师《MySQL 实战 45 讲》课程的学习笔记,并进行了一定的知识扩充。 sql 查询语句的执行流程 大体来说,MySQL 可以分为 Server 层和存储引擎层两部分。 Server 层包括连接器、查询缓存、分析器、优化器和执行器。 连接器负责接收客…...
仓颉编程语言入门 -- Array数组详解
仓颉编程语言入门 – Array数组详解 一. 如何创建Array数组 我们可以使用 Array 类型来构造单一元素类型,有序序列的数据。 1.仓颉使用 Array 来表示 Array 类型。T 表示 Array 的元素类型,T 可以是任意类型 , 类似于泛型的概念 var arr:Array<St…...
C#初级——简单单例模式使用
单例模式 单例模式是一种常用的软件设计模式,它确保一个类只有一个实例,并提供一个全局访问点来获取这个实例,通过单例模式防止私有成员被多次引用,防止数据被随意纂改。本文使用的是线程不安全的懒汉式单例。 创建单例模式 首…...
2024.07.29 校招 实习 内推 面经
地/球🌍 : neituijunsir 交* 流*裙 ,内推/实习/校招汇总表格 1、校招 | 美/团// 快驴、小象、优/选/事/业/部2024年校/园/招聘(内推) 校招 | 美团快驴、小象、优选事业部2024年校园招聘(内推ÿ…...
速盾:爬虫攻击和cc攻击的区别是什么?
爬虫攻击和CC(Distributed Denial of Service)攻击是网络安全领域两种不同类型的攻击方式。尽管它们都涉及对目标网站或服务器的非法访问,但它们的目的、方法和影响各不相同。在接下来的文章中,我们将详细介绍这两种攻击方式的区别…...
Tomcat与Nginx的区别详解
目录 引言Tomcat概述 Tomcat的历史Tomcat的架构Tomcat的功能Nginx概述 Nginx的历史Nginx的架构Nginx的功能Tomcat与Nginx的区别 架构上的区别...
【大模型从入门到精通5】openAI API高级内容审核-1
这里写目录标题 高级内容审核利用 OpenAI 内容审核 API 的高级内容审核技术整合与实施使用自定义规则增强审核综合示例防止提示注入的策略使用分隔符隔离命令理解分隔符使用分隔符实现命令隔离 高级内容审核 利用 OpenAI 内容审核 API 的高级内容审核技术 OpenAI 内容审核 AP…...
JVM系列 | 对象的消亡3——垃圾收集器的对比与实现细节
垃圾收集器 文章目录 各收集器简单对比收集器启动参数各收集器详细说明JDK 1.3 之前JDK 1.3 | SerialJDK 1.4 | ParNewJDK 1.4 | Parallel ScavengeJDK 5 | CMS 收集器JDK 7 | G1 各收集器简单对比 收集器名称出现时间淘汰时间目标采用技术线程数STW分代备注无名JDK 1.3之前JD…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
