当前位置: 首页 > 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…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

鸿蒙HarmonyOS 5军旗小游戏实现指南

1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;采用DevEco Studio实现&#xff0c;包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...

使用ch340继电器完成随机断电测试

前言 如图所示是市面上常见的OTA压测继电器&#xff0c;通过ch340串口模块完成对继电器的分路控制&#xff0c;这里我编写了一个脚本方便对4路继电器的控制&#xff0c;可以设置开启时间&#xff0c;关闭时间&#xff0c;复位等功能 软件界面 在设备管理器查看串口号后&…...