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

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...