当前位置: 首页 > news >正文

【数据结构与算法 | 图篇】Bellman-Ford算法(单源最短路径算法)

1. 前言

前文的迪杰斯特拉算法不能求解有负边的图的最短路径的问题。而此文的Bellman-Ford可以处理含负权边的图算法,并且能检测出图中是否存在负环(权重和为负数的环).

2. 基本思想

1. 初始化:

  • 对于所有顶点 v ∈ V \ {s}(除了起点 s),设其到起点的距离为无穷大(表示不可达)。
  • 起点 s 到自身的距离设为 0。


2. 松弛操作:

  • 遍历图中的每条边 (u, v) ∈ E,执行松弛操作 `Relax(u, v, w)`。松弛操作尝试通过边 (u, v) 更新从起点 s 到顶点 v 的已知最短距离。
  • 如果存在一条从起点 s 到顶点 u 的更短路径,并且这条路径加上边 (u, v) 的权重小于目前记录的从起点 s 到顶点 v 的距离,则更新顶点 v 的距离值。
  • 这个过程需要重复进行 |V| - 1 次(V 是顶点集)。因为在没有负权环的情况下,任何从起点到某个顶点的最短路径最多包含 |V| - 1 条边。

3. 检查负权环:

  •  在进行了 |V| - 1 轮松弛操作之后,再进行一轮松弛操作。如果在这个过程中仍然能够进一步减少某个顶点的距离值,那么说明图中存在一个可以被利用来无限降低路径成本的负权环。

3. 顶点类代码

public class Vertex {// 顶点的名字,用来区分顶点String name;// 与该顶点有关的边的集合List<Edge> edges;// 判断是否已经被遍历boolean visited = false;// 初始距离为无穷大int dist = INF;// INF表示无穷大final static int INF = Integer.MAX_VALUE;// 该顶点在最短路径中的前一个顶点Vertex prev = null;public Vertex(String name) {this.name = name;}public String getName() {return name;}
}

顶点图:

4. Bellman-Ford算法代码

public class BellmanFord {public static void main(String[] args) {Vertex v1 = new Vertex("1");Vertex v2 = new Vertex("2");Vertex v3 = new Vertex("3");Vertex v4 = new Vertex("4");v1.edges = new ArrayList<>();v1.edges.add(new Edge(v2, 2));v1.edges.add(new Edge(v3, 1));v2.edges = new ArrayList<>();v2.edges.add(new Edge(v3, -2));v3.edges = new ArrayList<>();v3.edges.add(new Edge(v4, 1));v4.edges = new ArrayList<>();List<Vertex> graph = new ArrayList<>();graph.add(v1);graph.add(v2);graph.add(v3);graph.add(v4);// v1作为起始点bellmanford(graph, v1);}public static void bellmanford(List<Vertex> graph, Vertex source){// 将起始点的距离设置为0,其余点的距离都是无穷大source.dist = 0;int size = graph.size();// 进行 顶点数-1 次处理for(int k = 0; k < size - 1; k++) {// 遍历所有的边for(Vertex v : graph){for(Edge e : v.edges){// 处理每条边if(v.dist != Integer.MAX_VALUE &&v.dist + e.weight < e.linked.dist){e.linked.dist = v.dist + e.weight;e.linked.prev = v;}}}}for(Vertex v : graph){System.out.println("v" + v.name + "  " + v.dist);}}
}

打印的结果:

v1  0
v2  2
v3  0
v4  1

相关文章:

【数据结构与算法 | 图篇】Bellman-Ford算法(单源最短路径算法)

1. 前言 前文的迪杰斯特拉算法不能求解有负边的图的最短路径的问题。而此文的Bellman-Ford可以处理含负权边的图算法&#xff0c;并且能检测出图中是否存在负环&#xff08;权重和为负数的环&#xff09;. 2. 基本思想 1. 初始化&#xff1a; 对于所有顶点 v ∈ V \ {s}&am…...

Python | Leetcode Python题解之第336题回文对

题目&#xff1a; 题解&#xff1a; class Solution:def palindromePairs1(self, words: List[str]) -> List[List[int]]:# 核心思想--枚举前缀和后缀# 如果两个字符串k1&#xff0c;k2组成一个回文字符串会出现三种情况# len(k1) len(k2),则需要比较k1 k2[::-1]# len(k1…...

C语言家教记录(六)

导语 本次授课的内容如下&#xff1a;指针&#xff0c;指针和数组 辅助教材为 《C语言程序设计现代方法&#xff08;第2版&#xff09;》 指针 指针变量 计算机按字节划分地址&#xff0c;每个地址访问一个字节 指针变量指向变量的地址&#xff0c;指的是变量第一个字节的…...

C++竞赛初阶L1-11-第五单元-for循环(25~26课)519: T454430 人口增长问题

题目内容 假设目前的世界人口有 x 亿&#xff0c;按照每年 0.1% 的增长速度&#xff0c;n 年后将有多少人&#xff1f; 输入格式 一行两个正整数 x 和 n&#xff0c;之间有一个空格。其中&#xff0c;1≤x≤100,1≤n≤100。 输出格式 一行一个数&#xff0c;表示答案。以亿…...

demo测试

目录 接口commonCodeGenerator entityuser mapperUserMapper controllerUserController serviceUserServiceimplUserServiceImpl mapper.xmlpom.xmlapplication.yml 接口 common CodeGenerator package com.llz.demo.common;import com.baomidou.mybatisplus.core.exceptions…...

TinTinLand Web3 + DePIN 共学月|深入探索 DePIN 项目,全景分析去中心化网络未来

「TinTinLand Web3 主题共学月」是由 TinTinLand 每月发起的主题学习活动&#xff0c;携手知名项目共同打造一个系统化、互动性强的学习平台&#xff0c;帮助开发者不断提升技能&#xff0c;紧跟 Web3 技术的前沿发展。活动通过演示视频、学习打卡、模拟环境、实际操作等多种方…...

Java并发编程(六)

1、java 中有几种方法可以实现一个线程 继承 Thread 类实现 Runnable 接口实现 Callable 接口&#xff0c;需要实现的是 call() 方法 2、如何停止一个正在运行的线程 使用共享变量的方式 在这种方式中&#xff0c;之所以引入共享变量&#xff0c;是因为该变量可以被多个执行…...

k8s对外服务之Ingress

目录 1.Ingress 简介 2.Ingress 组成 3.Ingress-Nginx 工作原理 4.部署 nginx-ingress-controller 5.总结 1.Ingress 简介 service的作用体现在两个方面&#xff0c;对集群内部&#xff0c;它不断跟踪pod的变化&#xff0c;更新endpoint中对应pod的对象&#xff0c;提供了…...

使用Python+moviepy在视频画面上绘制边框

一、 使用VideoFileClip对象的的fx函数设置vfx.margin&#xff0c;在视频画面上绘制边框 from moviepy.editor import * mvVideoFileClip(/home/Download/leaves.mp4) mv2mv.fx(vfx.margin,mar3,color(0,0,255),opacity0.5) # 绘制边框# mar3 &#xff1a;边框宽度3像素&#…...

灵办AI探索之旅:颠覆传统的代码开发工具

前言 灵办AI是一个先进的人工智能工具&#xff0c;专注于提高软件开发和项目管理的效率。其核心功能包括代码生成、优化、评估和自动化修复&#xff0c;旨在帮助开发者和团队提升开发速度和代码质量。 体验地址&#xff1a;https://ilingban.com/browser_extension/?fromjj …...

【Redis】Redis 数据类型与结构—(二)

Redis 数据类型与结构 一、值的数据类型二、键值对数据结构三、集合数据操作效率 一、值的数据类型 Redis “快”取决于两方面&#xff0c;一方面&#xff0c;它是内存数据库&#xff0c;另一方面&#xff0c;则是高效的数据结构。 Redis 键值对中值的数据类型&#xff0c;也…...

Tomcat初篇

目录 Tomcat主要特点Tomcat的核心组件Tomcat使用安装Tomcat配置Tomcat启动和停止Tomcat Tomcat工作原理目录结构配置文件性能优化策略 Tomcat Apache Tomcat是一个开源的Servlet容器和Web服务器&#xff0c;广泛用于运行基于Java的Web应用程序。它实现了Java Servlet和JavaSer…...

机器学习(2)-- KNN算法之手写数字识别

KNN算法 KNN&#xff08;K-Nearest Neighbor&#xff0c;K最近邻&#xff09;算法是一种用于分类和回归的非参数统计方法&#xff0c;尤其在分类问题中表现出色。在手写数字识别领域&#xff0c;KNN算法通过比较测试样本与训练样本之间的距离&#xff0c;找到最近的K个邻居&am…...

【机器人】关于钉钉机器人如何进行自定义开发问答【详细清晰】

目标&#xff1a;当用户输入问题并钉钉机器人&#xff0c;钉钉机器人进行相应的回答&#xff0c;达到一种交互问答的效果 开发文档参考&#xff1a;https://open.dingtalk.com/document/orgapp/robot-overview 首先进行登录企业&#xff0c;后面如果没有进行登录&#xff0c;会…...

Qt:exit,quit,close的用法及区别

前言 虽然能从单词的字面意思大致理解这些函数的意思&#xff0c;但是总感觉不出来它们的区别以及用法&#xff0c;特地去研究一下 正文 在 Qt 中&#xff0c;quit、exit 和 close 都是用于终止程序或关闭窗口的方法 1. QApplication::quit() 注意&#xff1a;注意quit() …...

Linux——进程地址空间

前言 在操作系统中&#xff0c;内存分为以下几个区域&#xff0c;从下往上按照从小到大排列 一、程序地址的分布 代码 #include <stdio.h> #include <stdlib.h> int noval; int val 1;int main(int argc,char*argv[],char*env[]){printf("code addr %p\n&q…...

信创(国产化)方案

信创 信创,即信息技术应用创新,旨在实现信息技术自主可控openEuler openEuler是一款开源、免费的操作系统,由openEuler社区运作,前身为运行在华为公司通用服务器上的操作系统EulerOS。openEuler作为一款开源、免费的操作系统,由开放原子开源基金会(OpenAtom Foundation)…...

EasyRecovery17中文版永久汉化版电脑数据恢复工具下载

&#x1f388;&#x1f389;安利时间到&#xff01;今天要跟大家分享的是——EasyRecovery17中文版的最新功能&#xff01;&#x1f389;&#x1f388; &#x1f31f;✨ “数据恢复小能手” ✨&#x1f31f; 让我来介绍一下这款软件的主打特点。 EasyRecovery17中文版是一款强…...

Cesium倾斜相机视角观察物体

先看效果&#xff1a; 在cesium中&#xff0c;我们有时需要倾斜相机视角去观察物体&#xff0c;如相机俯视45观察物体。 cesium的api提供了倾斜相机视角的配置&#xff0c;但是直接使用cesium的api不能达到我们想要的效果。 函数如下&#xff1a; function flyToBox() {let l…...

C/C++开发---全篇

1、统筹 学习目标&#xff1a; C/C、python精通。 就业匹配方向&#xff1a;专精一个领域&#xff0c;延长职业生涯。 &#xff08;1&#xff09;适配行业&#xff1b; &#xff08;2&#xff09;量化&#xff1b; &#xff08;3&#xff09;安全&#xff1b; &#xff08;4&…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

HTML版英语学习系统

HTML版英语学习系统 这是一个完全免费、无需安装、功能完整的英语学习工具&#xff0c;使用HTML CSS JavaScript实现。 功能 文本朗读练习 - 输入英文文章&#xff0c;系统朗读帮助练习听力和发音&#xff0c;适合跟读练习&#xff0c;模仿学习&#xff1b;实时词典查询 - 双…...

宠物车载安全座椅市场报告:解读行业趋势与投资前景

一、什么是宠物车载安全座椅&#xff1f; 宠物车载安全座椅是一种专为宠物设计的车内固定装置&#xff0c;旨在保障宠物在乘车过程中的安全性与舒适性。它通常由高强度材料制成&#xff0c;具备良好的缓冲性能&#xff0c;并可通过安全带或ISOFIX接口固定于车内。 近年来&…...

【向量库】Weaviate概述与架构解析

文章目录 一、什么是weaviate二、High-Level Architecture1. Core Components2. Storage Layer3. 组件交互流程 三、核心组件1. API Layer2. Schema Management3. Vector Indexing3.1. 查询原理3.2. 左侧&#xff1a;Search Process&#xff08;搜索流程&#xff09;3.3. 右侧&…...

Ansible+Zabbix-agent2快速实现对多主机监控

ansible Ansible 是一款开源的自动化工具&#xff0c;用于配置管理&#xff08;Configuration Management&#xff09;、应用部署&#xff08;Application Deployment&#xff09;、任务自动化&#xff08;Task Automation&#xff09;和编排&#xff08;Orchestration&#xf…...