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

Dijkstra求最短路篇二(全网最详细讲解两种方法,适合小白)(python,其他语言也适用)

前言:

Dijkstra算法博客讲解分为两篇讲解,这两篇博客对所有有难点的问题都会讲解,小白也能很好理解。看完这两篇博客后保证收获满满。

第一篇博客讲解朴素Dijkstra算法Dijkstra求最短路篇一(全网最详细讲解两种方法,适合小白)(python,其他语言也适用),本篇博客讲解堆优化Dijkstra算法,两中算法思路大体相同,但时间复杂度有所区别。

  • 朴素Dijkstra算法:时间复杂度 O ( n 2 ) O(n^2) O(n2)
  • 堆优化Dijkstra算法:时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn)

两篇博客给出的题目内容一样,只有数据规模不一样。

题目:

题目链接:
850. Dijkstra求最短路 II

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。
如果路径不存在,则输出 −1。

数据范围(两题不同处)
1 ≤ n , m ≤ 1.5 × 1 0 5 1≤n,m≤1.5×10^5 1n,m1.5×105,
图中涉及边长均不小于 0,且不超过 10000。
数据保证:如果最短路存在,则最短路的长度不超过 1 0 9 10^9 109

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

思路:

算法分析:
在这里插入图片描述

依旧是Dijkstra算法求解,不同的是本题需要降低时间复杂度。

对朴素Dijkstra算法时间复杂度分析可知:

  • 寻找路径最短的点: O ( n 2 ) O(n^2) O(n2)
  • 加入集合S: O ( n ) O(n) O(n)
  • 更新距离: O ( m ) O(m) O(m)
  • 所以总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

所以我们需要对寻找路径最短的点进行改变,如何降低找最短距离的点的时间复杂度呢?
这里可以使用最小堆进行优化(也就是优先队列),对优先队列不太熟悉的可以看看优先队列这篇博客,其他博主写的很详细这里我就不介绍了。

进行优化后时间复杂度分析如下:

  • 寻找路径最短的点: O ( n ) O(n) O(n)
  • 加入集合S: O ( n ) O(n) O(n)
  • 更新距离: O ( m l o g n ) O(mlogn) O(mlogn)

堆的数据结构大家接触的可能有点少,python中有专门的库函数可以直接使用,其他语言也有类似的库函数可以使用。

构造邻接表:

首先对数据进行存储,图的存储有两种方式,一种是邻接表,一种是邻接矩阵。题目中的数据规模用邻接表存储(本题数据规模是稀疏图)。

为什么要用邻接表去存贮,而不是邻接矩阵?

我们采用邻接矩阵还是采用邻接表来表示图,需要判断一个图是稀疏图还是稠密图。稠密图指的是边的条数|E|接近于|V|²,稀疏图是指边的条数|E|远小于于|V|²(数量级差很多)。本题是稠密图,显然稠密图用邻接矩阵存储比较节省空间,反之用邻接表存储。

邻接表存储就不需要注意重边和自环了,因为算法会自动算出最优解

邻接矩阵存储代码如下:

n, m = map(int, input().split())  # 图的节点个数和边数
#  构建邻接表 
num = [[] for i in range(n + 1)]
for _ in range(m):a, b, c = map(int, input().split())num[a].append((b, c))  # 无需考虑重边和自环

以题目实例为例,打印num数组

[[], [(2, 2), (3, 4)], [(3, 1)], []]

邻接表构建完成之后就要进行Dijkstra算法,这里直接给出代码,用详细代码给大家进行讲解。整体思路跟朴素Dijkstra算法大致相同

代码及详细注释:

import heapqn, m = map(int, input().split())  # 图的节点个数和边数
#  构建邻接表 
num = [[] for i in range(n + 1)]
for _ in range(m):a, b, c = map(int, input().split())num[a].append((b, c))  # 无需考虑重边和自环
dist = [float("inf") for _ in range(n + 1)]  # float("inf")在python中是无限大的意思
dist[1] = 0  # 源点到源点的距离为置为 0
state = [False for i in range(n + 1)]  # state 用于记录该点的最短距离是否已经确定def dijstra():# 这里heap中为什么要存两个值呢,首先小根堆是根据距离来排的,所以有一个变量要是距离,# 其次在从堆中拿出来的时候要知道知道这个点是哪个点,不然怎么更新邻接点呢?所以第二个变量要存点。heap = [(0, 1)]  # 首先放入距离0和点1,这个顺序不能倒,这里显然要根据距离排序while heap:distance, i = heapq.heappop(heap)  # 这里是取出最下距离和对应的点,最小堆自动取出最小值if state[i]:  # 如果该点最短距离已经确定,跳过下面操作continuestate[i] = True  # 标记该点距离确定for j, d in num[i]:  # 循环遍历找点i所能到的点和其距离if dist[j] > distance + d:  # 如果原本点j到源点的距离大于后续计算出来的值dist[j] = distance + d  # 更新heapq.heappush(heap, (dist[j], j))  # 该点距离和点加入到最小堆中# 判断最后一个点的最短距离是否找到,如果为无穷大,则表示未找到,返回-1,否则返回最短距离dist[-1]if dist[n] == float("inf"):return -1else:return dist[n]print(dijstra())

朴素Dijkstra算法大家理解好了本算法也很好理解,操作都是一样,只是在寻找路径最短的点时用了最小堆操作。这里就不拿实例带大家过了,如果略微有点懵,大家可以自己拿实例数据过一遍。

本题主要对 Python 中的 heapq 库进行简略讲解。

import heapqheap = []
heapq.heappush(heap, (1, 2))
heapq.heappush(heap, (1, 3))
heapq.heappush(heap, (2, 1))
heapq.heappush(heap, (2, 0))
heapq.heappush(heap, (0, 2))
heapq.heappush(heap, (0, 0))print("初始状态", heap)
print("删除的元素", heapq.heappop(heap))
print("删除后状态", heap)

运行结果:

初始状态 [(0, 0), (1, 2), (0, 2), (2, 0), (1, 3), (2, 1)]
删除的元素 (0, 0)
删除后状态 [(0, 2), (1, 2), (2, 1), (2, 0), (1, 3)]
  • heapq.heappush((heap, (1, 2)):把元素(1,2)加入到堆 heap中(每次加入后都是最小堆的构建形式)。
  • heapq.heappop(heap):弹出堆顶元素(最小堆的堆顶就是最小元素)。

总结:

堆优化版dijkstra适合稀疏图

思路:

堆优化版的dijkstra是对朴素版dijkstra进行了优化,在朴素版dijkstra中时间复杂度最高的寻找距离
最短的点O(n^2)可以使用最小堆优化。

  1. 一号点的距离初始化为零,其他点初始化成无穷大。
  2. 将一号点放入堆中。
  3. 不断循环,直到堆空。每一次循环中执行的操作为:
    弹出堆顶(与朴素版diijkstra找到S外距离最短的点相同,并标记该点的最短路径已经确定)。
    用该点更新临界点的距离,若更新成功就加入到堆中。

时间复杂度分析

  • 寻找路径最短的点: O ( n ) O(n) O(n)
  • 加入集合S: O ( n ) O(n) O(n)
  • 更新距离: O ( m l o g n ) O(mlogn) O(mlogn)

相关文章:

Dijkstra求最短路篇二(全网最详细讲解两种方法,适合小白)(python,其他语言也适用)

前言: Dijkstra算法博客讲解分为两篇讲解,这两篇博客对所有有难点的问题都会讲解,小白也能很好理解。看完这两篇博客后保证收获满满。 第一篇博客讲解朴素Dijkstra算法Dijkstra求最短路篇一(全网最详细讲解两种方法,适合小白)(p…...

Dijkstra求最短路篇一(全网最详细讲解两种方法,适合小白)(python,其他语言也适用)

前言: Dijkstra算法博客讲解分为两篇讲解,这两篇博客对所有有难点的问题都会讲解,小白也能很好理解。看完这两篇博客后保证收获满满。 本篇博客讲解朴素Dijkstra算法,第二篇博客讲解堆优化Dijkstra算法Dijkstra求最短路篇二(全网…...

计算机组成原理06:浮点数运算

浮点数加减运算 之前我们提到过&#xff0c;浮点数具有特定的表示形式。因此&#xff0c;在进行浮点数的加减运算之前&#xff0c;需要统一浮点数的表达方式。这里我们主要对浮点数表示中的尾数M进行处理&#xff0c;要求0≤M<1&#xff0c;统一格式如下&#xff1a; 正数…...

opencascade 快速显示AIS_ConnectedInteractive源码学习

AIS_ConcentricRelation typedef PrsDim_ConcentricRelation AIS_ConcentricRelation AIS_ConnectedInteractive 简介 创建一个任意位置的另一个交互对象实例作为参考。这允许您使用连接的交互对象&#xff0c;而无需重新计算其表示、选择或图形结构。这些属性是从您的参考对…...

CentOS系统上安装单机版Redis教程

一、前言 1.1 为什么选择Redis&#xff1f; Redis不仅支持丰富的数据类型&#xff08;如字符串、哈希、列表、集合、有序集合等&#xff09;&#xff0c;还具有高性能、持久化、发布订阅、事务和Lua脚本等特点。这些优势使其成为分布式系统和高并发应用中的首选。 1.2 为什么…...

纯Java实现Google地图的KMZ和KML文件的解析

目录 前言 一、关于KMZ和KML 1、KMZ是什么 2、KML是什么 二、Java解析实例 1、POM.xml引用 2、KML 基类定义 3、空间对象的定义 4、Kml解析工具类 三、KML文件的解析 1、KML解析测试 2、KMZ解析测试 四、总结 前言 今天是六.一儿童节&#xff0c;在这里祝各位大朋友…...

k8s自定义资源你会创建吗

创建自定义资源定义 CustomResourceDefinition 当你创建新的 CustomResourceDefinition&#xff08;CRD&#xff09;时&#xff0c;Kubernetes API 服务器会为你所 指定的每一个版本生成一个 RESTful 的 资源路径。CRD 可以是名字空间作用域的&#xff0c;也可以是集群作用域的…...

CATIA二次开发VBA入门(4)——进程外开发环境搭建,vb.net在Visual Studio中开发,创建圆柱曲面的宏录制到二次开发案例

目录 引出vb.net和vb6.0 进程外开发环境搭建vb.net开发环境搭建《CATIA二次开发技术基础》模板 添加宏库引用 vs开发环境初步vs中的立即窗口对象浏览器 建立模板案例&#xff1a;创建一堆圆柱曲面第一步&#xff1a;录制宏第二步&#xff1a;代码精简第三步&#xff1a;for循环…...

c++字符串相关接口

c字符串相关接口 1.str2wstr(str转换wstr)2.wstr2str(str转换wstr)3.Utf8ToAsi(Utf8转换ANSI)4.AsiToUtf8(ANSI转换Utf8)5.stringformatA/stringformatW(按照指定的格式格式化字符串)6.GetStringBetween(获取cStart cEnd之间的字符串)7.Char2Int(char转int)8.Str2Bin(字符串转换…...

Maven打包错误:无效的源发行版:17

1. 报错问题 在用maven进行打包时&#xff08;clean & install&#xff09;&#xff0c;报如下错误&#xff1a; 一开始让我很摸不着头脑&#xff0c;我确定我的pom.xml&#xff0c;还有IDEA中的Project Settings是正确的。 2. 排查 尽管确定&#xff0c;但还是一个个排…...

【环境栏Composer】Composer常见问题(持续更新)

1、执行composer install提示当前目录中没有 composer.lock 文件时 No composer.lock file present. Updating dependencies to latest instead of installing from lock file. See https://getcomposer.org/install for more information. Composer 在执行 install 命令时会…...

塑造更智慧的AI:策略与路径探索

提升数据质量&#xff1a; 数据清洗&#xff1a;去除数据中的异常值、缺失值、噪声等干扰因素&#xff0c;确保数据的准确性和一致性。数据标注&#xff1a;为数据集提供准确的标签&#xff0c;以便进行有监督学习。标注的质量直接影响模型的性能。数据增强&#xff1a;通过图像…...

软设之快速排序

快速排序是冒泡排序的改进算法 它采用的是分治法&#xff0c;基本思想是把原问题分解为若干规模更小但结构与原问题相似的子问题&#xff0c;通过递归解决这些子问题&#xff0c;然后将这些子问题的解组合成原问题的解。 它的步骤是 1.在待排序的n个记录中任取一个记录&…...

从零学算法2965

2965. 找出缺失和重复的数字 给你一个下标从 0 开始的二维整数矩阵 grid&#xff0c;大小为 n * n &#xff0c;其中的值在 [1, n2] 范围内。除了 a 出现 两次&#xff0c;b 缺失 之外&#xff0c;每个整数都 恰好出现一次 。 任务是找出重复的数字a 和缺失的数字 b 。 返回一个…...

【Mac版】Java生成二维码

软件版本 IntelliJ IDEA&#xff1a;2023.2 JDK&#xff1a;17 Tomcat&#xff1a;10.1.11 Maven&#xff1a;3.9.3 技术栈 servlet谷歌的&#xff1a;zxing 生成普通的黑白二维码在二维码中间添加一个小图标 github开源项目&#xff1a;qrcode qrcode开源项目的内部是基于z…...

ROS2自定义服务接口

ROS2自定义服务接口 在src/village_interface 下构建srv文件夹 src/village_interface/srv 下新建一个BorrowMoney.srv 遵循大小写编程规范 # 客户端请求 string name uint32 money # 中间这三个横杠很重要 不能删掉 --- # 服务端响应 bool success uint32 money接口编译 修改…...

linux /www/server/cron内log文件占用空间过大,/www/server/cron是什么内容,/www/server/cron是否可以删除

linux服务器长期使用宝塔自带计划任务&#xff0c;计划任务执行记录占用服务器空间过大&#xff0c;导致服务器根目录爆满&#xff0c;需要长期排查并删除 /www/server/cron 占用空间过大问题处理 /www/server/cron是什么内容&#xff1f;/www/server/cron是否可以删除&#xf…...

C++青少年简明教程:break语句、continue语句

C青少年简明教程&#xff1a;break语句、continue语句 break语句 只能用在switch语句和循环语句&#xff08;for循环、while循环和do-while循环&#xff09;中。作用&#xff1a;跳出switch语句或提前终止循环。 break语句的基本语法如下&#xff1a; break; break语句的示例…...

MySQL实战行转列(或称为PIVOT)实战sales的表记录了不同产品在不同月份的销售情况,进行输出

有一个sales的表&#xff0c;它记录了不同产品在不同月份的销售情况&#xff1a; productJanuaryFebruaryMarchProduct AJanuary10Product AFebruary20Product BJanuary5Product BFebruary15Product CJanuary8Product CFebruary12 客户需求展示为如下的样子&#xff1a; pro…...

牛客NC164 最长上升子序列(二)【困难 贪心+二分 Java/Go/PHP/C++】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237 思路 贪心二分 所谓贪心&#xff0c;就是往死里贪&#xff0c;所以对于最大上升子序列&#xff0c;结尾元素越小&#xff0c;越有利于后面接上其他的数&#xff0c;也就可能变…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

生信服务器 | 做生信为什么推荐使用Linux服务器?

原文链接&#xff1a;生信服务器 | 做生信为什么推荐使用Linux服务器&#xff1f; 一、 做生信为什么推荐使用服务器&#xff1f; 大家好&#xff0c;我是小杜。在做生信分析的同学&#xff0c;或是将接触学习生信分析的同学&#xff0c;<font style"color:rgb(53, 1…...