图论(四)—最短路问题(Dijkstra)

一、最短路

        概念:从某个点 A 到另一个点B的最短距离(或路径)。从点 A 到 B 可能有多条路线,多种距离,求其中最短的距离和相应路径。

        最短路径分类:

        单源最短路:图中的一个点到其余各点的最短路径

        多源最短路:图中任意两点的最短路径

         框架图解:

二、朴素Dijkstra算法

        算法思想(仅限于非负权重值):从起始点开始,使用贪心的策略,通过加点的方法,每次遍历到起始点距离最近且未被访问过的邻接节点 t ,将 t 加入到集合 S 中,直到访问过所有节点。

     通过 N 次循环确定 n 个点到起点的最短路距离 

        时间复杂度为 O(n^{2})

        1.在没有确定最短路中的所有点(集合 S 以外)找出距离起点最近的点 t   

        2.对 t 进行标记,加入到集合中

        3.用 t 更新其他点的最短路距离

       集合 S :已经确定最短路的点(被访问过的点)

        定义数组 dis:从起始点到某点 ( 3 号节点 ) 的最短距离( dis[3] )

        定义二维数组add: 

                add[u][v] 表示从 节点 u 到 节点 v 的距离(区分单向与双向,双向则add[v][u]=add[u][v]

      初始化: dis[1]=0 \, \, \, \, \, \, \, \, \, dis[x]=+\bowtie \, \, \, \, \, \, \, \, \, 2\leq x\leq n (以节点 1 为起始点)

        若 节点 u 与 节点 v 之间没有路径,初始化为 add[u][v]=+\Join

      核心代码:

for(int i=1;i<=n;i++)
{int t=-1;for(int j=1;j<=n;j++)   // 在没有确定最短路中的所有点找出距离最短的那个点 t if(!s[j] && (t==-1||dis[t]>dis[j]))t=j;                  s[t]=true; // 代表 t 这个点已经确定最短路了for(int j=1;j<=n;j++) // 用 t 更新其他点的最短距离 dis[j] = min(dis[j],dis[t]+add[t][j]);
}

样例解释:对于下图,求出节点 A 的单源最短路 

 

n12345
dis07395

三、堆优化dijkstra算法

        在朴素dijkstra算法中,遍历点是通过for循环对所有节点判断一遍得出的,”对所有节点判断“这一操作消耗了更多的时间。

        算法思想:

        可以通过堆(优先队列)进行优化,堆(优先队列)存储节点起始点到该点最短距离,堆(优先队列)按照距离自动排序取距离最小且未被访问过的点,同通过用邻接链表(或邻接表)储存图的方法,再进行松弛操作,并将进行松弛操作的节点插入堆中。

         ①.初始化距离:数组dis 都初始化为 0x3f3f3f3f(无穷大),并将 1 号节点插入堆中 (dis[1]=0)

         ②取出堆顶的点(当前起始点到该点距离最小),判断是否被访问过,不断弹出取堆顶,直至找到未被访问的节点,再根据邻接链表(或邻接表)拓展。

         ③进行松弛操作,把松弛的点和距离插入到堆中。

        堆优化代码:

void dij(int s)
{priority_queue< pair<int,int> > q;  // 利用优先队列q.push(make_pair(0,s));memset(dis,127,sizeof(dis));dis[s]=0;while(q.size()){int u=q.top().second;q.pop();if(vis[u]==1) continue;vis[u]=1;for(int i=head[u];i;i=edge[i].next) // 链式前向星{int v=edge[i].to;int w=edge[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push(make_pair(-dis[v],v));  // 将路径以负数保存,优先队列默认大根堆}}}
}

关于dijkstra算法的正确性证明,参考博文:

Dijkstra贪心算法的准确性证明_为什么这种方法求下来的路径一定是最短?试分析一下它的正确性-CSDN博客

四、dijkstra算法不能用于有负权边的图

        通过上述dijkstra思想可以得出,每次松弛操作就是通过当前离起始点最近的点来更新其他点的距离,下面举例说明。

当此时通过 节点 4 更新其他节点, dijkstra 思想已经确定 dis [ 4 ] 为 起始点 到 节点 4 的最短路,显然错误。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/339883.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【图像处理与机器视觉】频率域滤波

知识铺垫 复数 CRjI 可以看作复平面上的点&#xff0c;则该复数的坐标为&#xff08;R&#xff0c;I&#xff09; 欧拉公式 e j θ c o s θ j s i n θ e^{j\theta} cos \theta j sin \theta ejθcosθjsinθ 极坐标系中复数可以表示为&#xff1a; C ∣ C ∣ ( c o s…

15、matlab绘图汇总(图例、标题、坐标轴、线条格式、颜色和散点格式设置)

1、plot()函数默认格式画图 代码: x=0:0.1:20;%绘图默认格式 y=sin(x); plot(x,y) 2、X轴和Y轴显示范围/axis()函数 代码: x=0:0.1:20;%绘图默认格式 y=sin(x); plot(x,y) axis([0 21 -1.1 1.1])%设置范围 3、网格显示/grid on函数 代码: x=0:0.1:20;%绘图默认格式 …

拓展虚拟世界边界,云手机可以做到吗

虚拟世界&#xff0c;AI&#xff0c;VR等词汇是21世纪最为流行的词汇&#xff0c;在科技背后&#xff0c;这些词汇的影响变得越来越大&#xff0c;已经走进了人们的世界&#xff0c;比如之前APPLE发布的vision pro&#xff0c;使人们能够更加身临其境的体验到原生os系统&#x…

从MLP到卷积

1.从MLP到卷积层 最近要做多通道的实验&#xff0c;所以重新将处理图像的基础模型回顾一下&#xff0c;什么是卷积&#xff1f;卷积本质是是一种特殊的全连接层。 1.1怎么w的权重从一个值变成了4维呢?可以这样理解&#xff0c;在此举一个例子&#xff1a; 其实本质可以看成&…

安防综合管理系统EasyCVR平台GA/T1400视图库:基于XML的消息体格式

GA/T 1400标准的应用范围广泛&#xff0c;涵盖了公安系统的视频图像信息应用系统&#xff0c;如警务综合平台、治安防控系统、交通管理系统等。在视频监控系统中&#xff0c;GA/T 1400公安视图库的对接是实现视频图像信息传输、处理和管理的重要环节。 以视频汇聚EasyCVR视频监…

Flink中因java的泛型擦除导致的报错及解决

【报错】 Exception in thread "main" org.apache.flink.api.common.functions.InvalidTypesException: The return type of function Custom Source could not be determined automatically, due to type erasure. You can give type information hints by using th…

使用Xshell一键在多个会话中执行多个命令

背景 平时在工作中经常通过ssh远程操作Linux&#xff0c;由于我们负责的服务部署在超过5台服务器&#xff08;相同的代码及路径&#xff09;&#xff0c;每次发布后执行重启都得重复操作5次关闭、检查、启动、查看日志&#xff0c;特别繁琐。 后来发现Xshell 7可以录制脚本&am…

【MyBatis】MyBatis操作数据库(二):动态SQL、#{}与${}的区别

目录 一、 动态SQL1.1 \<if>标签1.2 \<trim>标签1.3 \<where>标签1.4 \<set>标签1.5 \<foreach>标签1.6 \<include>标签 二、 #{}与${}的区别2.1 #{}是预编译sql&#xff0c;${}是即时sql2.2 SQL注入2.3 #{}性能高于${}2.4 ${}用于排序功能…

洛谷 P10566 「Daily OI Round 4」Analysis 题解

先弄个 ASCII 码表&#xff1a; 分析 很明显&#xff0c;想要节省时间&#xff0c;就要把这些字符转换成和它们的 ASCII 值最接近的大写字母。 通过 ASCII 码表&#xff0c;很容易就可以发现&#xff1a; ASCII 值与数字最接近的大写字母是 A \texttt A A。ASCII 值与小写…

JVM学习-监控工具(二)

jmap&#xff1a;导出内存映像文件&内存使用情况 基本情况 jmap(JVM Memory Map)&#xff1a;一方法获取dump文件(堆转储快照文件&#xff0c;二进制文件)&#xff0c;还可以获取目标Java进程的内存相关信息&#xff0c;包括Java堆各区域的使用情况、堆中对象的统计信息、…

多线程新手村5--线程池

1.1 线程池是什么 线程诞生的意义是因为进程的创建/销毁开销太大&#xff0c;所以使用线程提高代码的执行效率&#xff1b;那如果想要进一步提升执行效率&#xff0c;该怎么办呢&#xff1f;有一个方法是使用线程池。 首先&#xff0c;什么是线程池&#xff1a;池就是池子&am…

奶茶店、女装店、餐饮店是高危创业方向,原因如下:

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 现在的俊男靓女们&#xff0c;心中都有一个执念&#xff1a; (1)想证明自己了&#xff0c;开个奶茶去…… (2)想多赚点钱了&#xff0c;加盟餐饮店去…… (3)工作不顺心了&#xff0c;搞个女装店去…… 但凡抱着…

102.网络游戏逆向分析与漏洞攻防-ui界面的设计-反隐身功能的界面设计与实现(有不使用MFC生成,自己手写代码创建复选框与事件的例子)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 如果看不懂、不知道现在做的什么&#xff0c;那就跟着做完看效果&#xff0c;代码看不懂是正常的&#xff0c;只要会抄就行&#xff0c;抄着抄着就能懂了 内容…

独立游戏开发的 6 个步骤

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…

discuz论坛怎么修改备案信息

大家好&#xff0c;今天给大家分享下discuz如何填写备案信息并且展示在网站首页。大家都知道国内网站都需要备案&#xff0c;不通过备案的网站上是没办法通过域名打开的。大家也可以通过搜索网创有方&#xff0c;或者直接点击网创有方 查看悬挂备案号后的效果。 首先大家可以看…

MySQL表的增删改查初阶(上篇)

本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人…

成人本科毕业论文怎么写?分享自己的经验

撰写成人本科毕业论文是一个系统而深入的过程&#xff0c;以下是我个人的经验分享&#xff0c;希望能帮助你更好地完成这一任务&#xff1a; 1. 明确论文选题 兴趣与专长&#xff1a;选择自己感兴趣且有一定专长的领域&#xff0c;这样更容易深入研究。可行性&#xff1a;确保…

【全开源】种草分享|动态朋友圈|瀑布流|uniapp

一款基于FastadminThinkPHP和Uniapp开发的种草分享评论点赞消息提醒系统&#xff0c;发布动态&#xff0c;分享种草生活&#xff0c;可以收藏关注点赞&#xff0c;消息提醒&#xff0c;同时支持H5/小程序/app多端。 ​让每一次互动都不再错过&#x1f514; &#x1f331; 种草…

spring boot 中的异步@Async

spring boot 开启异步调用 1、启动类上添加EnableAsync注解&#xff0c;表示启动异步 2、在具体实现异步的方法上添加Async注解 package com.example.demo;import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootAppli…

HTML5的标签(文本链接、图片路径详解)

目录 前言 一、文本链接 超链接表述 二、图片路径详解 绝对路径 相对路径 网络路径 前言 一、文本链接 超链接表述 HTML 使用标签<a>来设置超文本链接 超链接可以是一个字&#xff0c;一个词&#xff0c;或者一组词&#xff0c;也可以是一幅图像&#xff0c;…