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

关于最短路径算法中边的权值的思考

关于最短路径算法中边的权值的思考

不管是单源最短路径算法:Dijkstra Bellman-ford
还是多源最短路径算法:floyed Johnson
我们都绕不开的一件事就是,边的权值wi,jw_{i,j}wi,j
下面我们从多个角度谈边的权值

1.权值恒定

它是指对于每条边的权值wi,jw_{i,j}wi,j,只要i,j确定,wi,jw_{i,j}wi,j就保持不变。这时,这张图应该是一个静态的图。

1.1 如果权值全部非负

这时我们可以将wi,jw_{i,j}wi,j理解为从节点i到节点j的距离,我们可以使用Dijkstra算法求出单源最短路径,但是此时我们无法使用Dijkstra求出单源最长路径,因为Dijkstra算法是一种贪心算法,他每次都找到最优的点,即距离最远的点,而最长路径中,不一定每一个点都是局部最优的。

所以我们说,Dijkstra算法只适用于全局最优要求局部最优的情况

不过如果我们使用Bellman-ford算法,我们就可以求出最长路径,而且能够判断是否存在正环。即我们的改动就是,“松弛操作”:

初始情况下,s.d=0,其他所有节点距离s点的距离为负无穷
//松弛边 Edge(u,v)
relax(u,v)if( v.d<u.d+w(u,d)v.d=u.d+w(u,d)

1.2 如果权值有正有负

这时我们不能采用Dijkstra算法求最长路径或者最短路径

但是,我们仍然可以使用Bellman-ford算法求出最短路径和最长路径,还能判断是否存在正环或者负环,这一切都取决于我们的松弛操作的设计

2.权值非恒定

这是指wi,jw_{i,j}wi,j,在i和j确定情况下,它还会随其他因素变化,最经典的情况就是,wi,j=f(i.d,j.d)w_{i,j}=f(i.d,j.d)wi,j=f(i.d,j.d)
即它和i j两点到源节点s的距离有关,而我们知道i.dj.d会随着程序运行而发生改变,即程序运行过程中,边的权值会发生改变。

此时我们仍然可以使用Bellman-ford算法来计算最短路径或者是最长路径。
这是因为,虽然随着程序的运行,每个节点v到源点s的距离会变化,但是我们要知道的是:Bellman-ford算法的终止情形是:不存在可松弛边

一种情况是:边权值的变化导致了v.d的变化,而v.d的变化又会导致了边权值的变化从而周而复始,无法结束,这时我们就称 这个图中存在负环或者正环,导致无法求出最短路径或者最长路径。

另一种情况是:你优化你的路径方案后,你去修改图的状态,如果此时你发现基于目前的图的状态,你无法继续优化你的路径方案,那就不会修改图的状态,那就意味者程序结束。这时我们的算法就成功找到了路径方案

所以,只要当方案不发生变化,即i.dj.d不发生变化 ,wi,jw_{i,j}wi,j就不在改变时,即使w_{i,j}会随着程序运行发送变化,我们仍然可以使用bellman-ford算法计算最长或最短路径

相关文章:

关于最短路径算法中边的权值的思考

关于最短路径算法中边的权值的思考 不管是单源最短路径算法&#xff1a;Dijkstra Bellman-ford 还是多源最短路径算法&#xff1a;floyed Johnson 我们都绕不开的一件事就是&#xff0c;边的权值wi,jw_{i,j}wi,j​ 下面我们从多个角度谈边的权值 1.权值恒定 它是指对于每条边…...

LVGL开发教程:二、ESP-IDF 使用CmakeList管理自己的文件以及文件夹

本文需要已经安装了Vscode+IDF插件没有安装的请提前安装一下,IDF插件为乐鑫的插件不需要翻墙。需要环境搭建请看下面链接。 环境搭建: VScode+platformIO和Vscode+ESP-IDF两种开发环境搭建 项目例程下载地址: IDF-CmakeTes,密码:8888 另外,由于你和我的路径不一致,下载的工…...

与感受野相关的几种网络结构

一、Inception 1. Inception v1 目的 通过设计一个稀疏网络结构&#xff0c;但是能够产生稠密的数据&#xff0c;既能增加神经网络表现&#xff0c;又能保证计算资源的使用效率。 结构 图1-1 Inception v1结构图 特点 共4个通道&#xff0c;其中3个卷积通道分别使用111111…...

day19_抽象类丶接口

由来 当我们声明一个几何图形类&#xff1a;圆、矩形、三角形类等&#xff0c;发现这些类都有共同特征&#xff1a;求面积、求周长、获取图形详细信息。那么这些共同特征应该抽取到一个公共父类中。但是这些方法在父类中又无法给出具体的实现&#xff0c;而是应该交给子类各自…...

【网安神器篇】——系统指纹探测工具finger

作者名&#xff1a;白昼安全主页面链接&#xff1a; 主页传送门创作初心&#xff1a; 以后赚大钱座右铭&#xff1a; 不要让时代的悲哀成为你的悲哀专研方向&#xff1a; web安全&#xff0c;后渗透技术每日鸡汤&#xff1a; 我不想停下&#xff0c;因为这次出发的感觉太好了一…...

Prometheus离线tar包安装

Prometheus离线tar包安装实验环境一、部署前操作二、Master2.1下载2.2解压2.3更改服务目录名称2.4创建系统服务启动文件2.5配置修改2.6启动并设置开机自启2.7访问2.8添加node节点2.8.1 添加方法2.8.2修改Prometheus配置&#xff08;Master&#xff09;————————————…...

PostgreSQL查询引擎——SELECT STATEMENTS SelectStmt

SelectStmt: select_no_parens %prec UMINUS| select_with_parens %prec UMINUS select_with_parens:( select_no_parens ) { $$ $2; }| ( select_with_parens ) { $$ $2; } 该规则返回单个SelectStmt节点或它们的树&#xff0c;表示集合操作树(set-operation tree…...

零信任-易安联零信任介绍(11)

​目录 ​易安联零信任公司介绍 易安联零信任发展路线 易安联零信任产品介绍 易安联零信任架构 易安联零信任解决方案 易安联零信任发展展望 易安联零信任公司介绍 易安联是一家专业从事网络信息安全产品研发与销售&#xff0c;是行业内领先的“零信任”解决方案提供商&…...

C++ STL——map和set的使用

文章目录1. 关联式容器1.1 键值对1.2 树形结构的关联式容器2. set2.1 set的介绍2.2 set的插入2.3 set的删除和查找2.4 lower_bound和upper_bound3. multiset3.1 count4. map4.1 map的介绍4.2 map的插入4.3 map的遍历4.4 map的[ ]5. multimap1. 关联式容器 我们之前学的vector、…...

【Python】thread使用

目录1、Condition条件变量使用2、event通信3、Semaphore信号量使用4、setDaemon设置守护线程5、threadPool_map使用6、threadPool使用7、threadingTimer1、Condition条件变量使用 # encoding:utf-8 Condition 提供了一种多线程通信机制&#xff0c; 假如线程 1 需要数据&#…...

计网传输层协议:UDP和TCP

文章目录一. 应用层和传输层的联系二. UDP协议三. TCP协议1. TCP报头介绍2. TCP实现可靠传输的核心机制2.1 确认应答2.2 超时重传3. 连接管理(三次握手, 四次挥手)3.1 建立连接(三次握手)3.2 断开连接(四次挥手)4. 滑动窗口5. 流量控制6.拥塞控制7. 延时应答8. 捎带应答9. 面向…...

一文讲明TCP网络编程、Socket套接字的讲解使用、网络编程案例

文章目录1 Socket讲解2 基于Socket的TCP编程3 客户端Socket的工作过程包含以下四个基本的步骤3.1 客户端创建Socket对象4 服务器程序的工作过程包含以下四个基本的步骤&#xff1a;4.1 服务器建立ServerSocket对象5 案例实现 客户端和服务端通信5.1 代码实现5.2 实现结果6 更多…...

Java中print和println的区别

1 问题在最开始学习Java的时候学到soutenter键可以输出结果&#xff0c;显示的是System.out.println()&#xff1b;而在Python中是直接使用print。那么在Java中print和println有什么区别&#xff1f;2 方法Print输出会自动将括号中的内容转换成字符串输出&#xff0c;如果括号中…...

RocketMq使用规范(纯技术和实战建议)

概述&#xff1a; 使用规范主要从&#xff0c;生产、可靠性、和消费为轴线定义使用规范&#xff1b;kafka使用核心&#xff1a;削峰、解耦、向下游并行广播通知&#xff08;无可靠性保证&#xff09;和分布式事务&#xff0c;本规范仅从削峰、解耦、向下游并行广播通知论述&am…...

matlab离散系统仿真分析——电机

目录 1.电机模型 2.数字PID控制 3.MATLAB数字仿真分析 3.1matlab程序 3.2 仿真结果 4. SIMULINK仿真分析 4.1simulink模型 4.2仿真结果 1.电机模型 即&#xff1a; 其中&#xff1a;J 0.0067&#xff1b;B 0.10 2.数字PID控制 首先我们来看一下连续PID&#xff1…...

一文学会进程控制

目录进程的诞生fork函数fork的本质fork的常规用法fork调用失败的原因进程的死亡进程退出的场景常见的进程退出方法正常终止&#xff08;代码跑完&#xff09;echo $?main函数返回调用exit调用_exitexit和_exit的区别进程等待进程等待的重要性进程等待的函数waitwaitpid进程退出…...

5.2 BGP水平分割

5.2.2实验2&#xff1a;BGP水平分割 1. 实验目的 熟悉BGP水平分割的应用场景掌握BGP水平分割的配置方法 2. 实验拓扑 实验拓扑如图5-2所示&#xff1a; 图5-2&#xff1a;BGP水平分割 3. 实验步骤 &#xff08;1&#xff09;配置IP地址 R1的配置 <Huawei>…...

华为OD机试 - TLV 编码 | 备考思路,刷题要点,答疑 【新解法】

最近更新的博客 【新解法】华为OD机试 - 关联子串 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试 - 停车场最大距离 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试 - 任务调度 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试…...

【C语言每日一题】——猜名次

【C语言每日一题】——猜名次&#x1f60e;前言&#x1f64c;猜名次&#x1f64c;解题思路分享&#xff1a;&#x1f60d;解题源码分享&#xff1a;&#x1f60d;总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右铭&#xff1a;全神…...

Agilent E4982A、Keysight E4982A、LCR 表,1 MHz 至 3 GHz

Agilent E4982A、Keysight E4982A、HP E4982A LCR 表&#xff0c;1 MHz 至 3 GHz 产品概览 KEYSIGHT E4982A&#xff08;安捷伦&#xff09; Keysight E4982A LCR 表为需要高频&#xff08;1 MHz 至 3 GHz&#xff09;阻抗测试的无源元件制造行业提供一流的性能&#xff0c…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...