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

【算法基础】Dijkstra 算法

定义:

  • g [ i ] [ j ] g[i][j] g[i][j] 表示 v i v_i vi 到 $v_j $的边权重,如果没有连接,则 g [ i ] [ j ] = ∞ g[i][j] = \infty g[i][j]=
  • d i s [ i ] dis[i] dis[i] 表示 v k v_k vk 到节点 v i v_i vi 的最短长度, d i s [ k ] = 0 , d i s [ i ] = ∞ , i ≠ k dis[k] = 0, dis[i]=\infty, i \neq k dis[k]=0,dis[i]=,i=k.

目标:

  • 计算出 d i s dis dis 数组,也就是任何点到 v k v_k vk 的距离。

step1 : 更新 v k v_k vk 的所有邻居节点 v y v_y vy的最短路径; 即: d i s [ y ] = g [ k ] [ y ] dis[y] = g[k][y] dis[y]=g[k][y]
step2 : 找出 这些邻居节点中路径最短的 d i s [ i 1 ] dis[i1] dis[i1]. 此时 d i s [ i 1 ] dis[i1] dis[i1] 一定已经是最短的了,可以用反证法来证明。
step3 : 找出 v i 1 v_{i1} vi1 的邻居节点 y ′ y' y, 如果 d i s [ i 1 ] + g [ i 1 ] [ y ′ ] < d i s [ y ′ ] dis[i1]+g[i1][y'] < dis[y'] dis[i1]+g[i1][y]<dis[y], 则更新 d i s [ y ′ ] = d i s [ i 1 ] + g [ i 1 ] [ y ′ ] dis[y'] =dis[i1]+g[i1][y'] dis[y]=dis[i1]+g[i1][y], 否则不更新。
step4 : 找出 k , i 1 k,i1 k,i1之外的 d i s [ i ] dis[i] dis[i] 最小的值 d i s [ i 2 ] dis[i2] dis[i2], 重复之前的更新过程,知道取完所有点为止。

code :

leecode 743
朴素写法:

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:g = [[inf for _ in range(n)] for _ in range(n)]  # 邻接矩阵for x, y, d in times:g[x - 1][y - 1] = ddis = [inf] * nans = dis[k - 1] = 0  # 起始节点done = [False] * n   #是否确定为最短while True:x = -1# 找到最短的 done 是用来排除已经确定的那些点的。完成后x 记录当前最短距离的那个点。# 起始为 kfor i, ok in enumerate(done):if not ok and (x < 0 or dis[i] < dis[x]):x = i# 没有找到,也就是所有点已经全部确定后。if x < 0:return ans  # 最后一次算出的最短路就是最大的# 无法到达if dis[x] == inf:  # 有节点无法到达return -1# 因为每次都是递增的,而答案是要求最大的最短路径。ans = dis[x]  # 求出的最短路会越来越大done[x] = True  # 最短路长度已确定(无法变得更小)# 更新 x 的邻居节点的最短距离。for y, d in enumerate(g[x]):# 更新 x 的邻居的最短路dis[y] = min(dis[y], dis[x] + d)

堆优化 Dijkstra:

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:g = [[] for _ in range(n)]  # 邻接表for x, y, d in times:g[x - 1].append((y - 1, d))dis = [inf] * ndis[k - 1] = 0h = [(0, k - 1)]   # 二元组 (dis[i], i)while h:dx, x = heappop(h)  # 找到最短路径的 x 和其相应的 disif dx > dis[x]:  # x 之前出堆过,continue# 这里continue 是因为 对于一个x 由于更新了多次dis, 堆中科恩那个存在多个 dx, 对于那些较大的dx, 不再使用的意思。# 更新邻居for y, d in g[x]:new_dis = dx + dif new_dis < dis[y]:dis[y] = new_dis  # 更新 x 的邻居的最短路heappush(h, (new_dis, y))mx = max(dis)return mx if mx < inf else -1

相关文章:

【算法基础】Dijkstra 算法

定义&#xff1a; g [ i ] [ j ] g[i][j] g[i][j] 表示 v i v_i vi​ 到 $v_j $的边权重&#xff0c;如果没有连接&#xff0c;则 g [ i ] [ j ] ∞ g[i][j] \infty g[i][j]∞ d i s [ i ] dis[i] dis[i] 表示 v k v_k vk​ 到节点 v i v_i vi​ 的最短长度&#xff0c; …...

使用 Flask 3 搭建问答平台(三):注册页面模板渲染

前言 前端文件下载 链接https://pan.baidu.com/s/1Ju5hhhhy5pcUMM7VS3S5YA?pwd6666%C2%A0 知识点 1. 在路由中渲染前端页面 2. 使用 JinJa 2 模板实现前端代码复用 一、auth.py from flask import render_templatebp.route(/register, methods[GET]) def register():re…...

pycharm如何debug for循环里面的错误值

一般debug时&#xff0c;在for循环里面的话&#xff0c;需要自己一步一步点。如果循环几百次那种就比较麻烦。此时可以采用try except的方式来解决 例子如下 #ptyhon debug for循环的代码 num[1,2,3,s,4] ans0 for i in num:try:ansiexcept:print(错误) print(ans) 结果如下&a…...

解决网页中的 video 标签在移动端浏览器(如百度访问网页)视频脱离文档流播放问题

问题现象 部分浏览器视频脱离文档流&#xff0c;滚动时&#xff0c;视频是悬浮出来&#xff0c;在顶部播放 解决方案 添加下列属性&#xff0c;可解决大部分浏览器的脱离文档流的问题 <videowebkit-playsinline""playsInlinex5-playsinlinet7-video-player-t…...

.Net--CLS,CTS,CLI,BCL,FCL

1.什么是CLS&#xff1f; 所以.NET专门为此参考每种语言(例如C# &#xff0c;VB&#xff0c;F#)并找出了语言间的共性&#xff0c;然后定义了一组规则&#xff0c;开发者都遵守这个规则来编码&#xff0c;那么代码就能被任意.NET平台支持的语言所通用。 而与其说是规则&#x…...

Stable Diffusion:质量高画风清新细节丰富的二次元大模型二次元插图

今天和大家分享一个基于Pony模型训练的二次元模型&#xff1a;二次元插图。关于该模型有4个不同的分支版本。 1.5版本&#xff1a;loar模型&#xff0c;推荐底模型niji-动漫二次元4.5。 xl版本&#xff1a;SDXL模型版本 mix版本&#xff1a;光影减弱&#xff0c;减少SDXL版本…...

数读MEME之争:以太坊获更高价值共识,抢占热点成Solana流量密码

在当前显著的加密牛市中&#xff0c;以太坊和Solana之间的竞争不仅在币价表现上显而易见&#xff0c;生态发展方面也备受关注。特别是在这轮MEME行情中&#xff0c;双方阵营的MEME代币呈现出不同的特点和趋势。 市场表现对比 以太坊的优势&#xff1a; 市场份额和认可度更高&…...

python的with语句

1.with语句的作用 在 Python 中&#xff0c;with 语句用于创建一个上下文管理器&#xff0c;以更简洁和安全的方式管理资源。 其主要优点是可以确保在代码块执行完毕后&#xff0c;相关资源能够被正确释放或清理&#xff0c;即使在代码块内部发生了异常。 以下是一个使用 with…...

Selenium原理深度解析

在自动化测试领域&#xff0c;Selenium无疑是最受欢迎和广泛使用的工具之一。它支持多种浏览器和操作系统&#xff0c;为开发人员和测试人员提供了强大的自动化测试解决方案。本文将深入探讨Selenium的工作原理&#xff0c;包括其架构、核心组件、执行流程以及它在自动化测试中…...

算法复杂度<数据结构 C版>

什么是算法复杂度&#xff1f; 简单来说算法复杂度是用来衡量一个算法的优劣的&#xff0c;一个程序在运行时&#xff0c;对运行时间和运行空间有要求&#xff0c;即时间复杂度和空间复杂度。 目录 什么是算法复杂度&#xff1f; 大O的渐近表达式 时间复杂度示例 空间复杂度…...

【XSS】

文章目录 0x01 简介0x02 XSS Payload用法XSS攻击平台及调试JavaScript 0x03 XSS绕过XSS漏洞防御策略 跨站脚本攻击&#xff0c;Cross Site Script。&#xff08;重点在于脚本script&#xff09; 有关XSS可以造成的 危害&#xff0c;见 0x02 XSS Payload用法 分类 反射型、存储…...

Go网络编程-RPC程序设计

gRPC 通信 RPC 介绍 RPC, Remote Procedure Call&#xff0c;远程过程调用。与 HTTP 一致&#xff0c;也是应用层协议。该协议的目标是实现&#xff1a;调用远程过程&#xff08;方法、函数&#xff09;就如调用本地方法一致。 如图所示&#xff1a; 说明&#xff1a; Servi…...

Linux 性能优化:轻松入门

文章目录 前言一、磁盘性能优化1、 磁盘 RAID 模式选择2、文件系统优化 二、优化 CPU1、性能监控 &#xff1a;2、进程优先级调整 &#xff1a;3、进程与 CPU 绑定 &#xff1a; 三、优化内存四、网络性能优化1、调整 TCP 缓冲区大小2、修改系统级别的文件描述符的数量3、调整 …...

C++相关概念和易错语法(22)(final、纯虚函数、继承多态难点)

1.final final在继承和多态中都可以使用&#xff0c;在继承中是指不想将自己被继承&#xff0c;在多态中是指不想该函数被重写&#xff0c;比较简单&#xff0c;下面是一些使用例子。 2.纯虚函数 当我们需要抽象一个类的时候&#xff0c;我们就需要用到纯虚函数。所谓抽象的类…...

状态管理的艺术:探索Flutter的Provider库

状态管理的艺术&#xff1a;探索Flutter的Provider库 前言 上一篇文章中&#xff0c;我们详细介绍了 Flutter 应用中的状态管理&#xff0c;以及 StatefulWidget 和 setState 的使用。 本篇我们继续介绍另一个实现状态管理的方式&#xff1a;Provider。 Provider优缺点 基…...

玩转HarmonyOS NEXT之IM应用首页布局

本文从目前流行的垂类市场中&#xff0c;选择即时通讯应用作为典型案例详细介绍HarmonyOS NEXT的各类布局在实际开发中的综合应用。即时通讯应用的核心功能为用户交互&#xff0c;主要包含对话聊天、通讯录&#xff0c;社交圈等交互功能。 应用首页 创建一个包含一列的栅格布…...

GPT-4o大语言模型优化、本地私有化部署、从0-1搭建、智能体构建

原文链接&#xff1a;GPT-4o大语言模型优化、本地私有化部署、从0-1搭建、智能体构建https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247608565&idx3&snd4e9d447efd82e8dd8192f7573886dab&chksmfa826912cdf5e00414e01626b52bab83a96199a6bf69cbbef7f7fe…...

记录些MySQL题集(4)

1、数据库的三范式是什么&#xff1f; 第一范式&#xff1a;列不可再分 第二范式&#xff1a;在第一范式的基础上&#xff0c;要求数据库表中的所有非主键列完全依赖于主键&#xff0c;而不是仅依赖于主键的一部分 第三范式&#xff1a;满足第二范式的基础上&#xff0c;所有…...

pdf提取其中一页怎么操作?提取PDF其中一页的方法

pdf提取其中一页怎么操作&#xff1f;需要从一个PDF文件中提取特定页码的操作通常是在处理文档时常见的需求。这种操作允许用户选择性地获取所需的信息&#xff0c;而不必操作整个文档。通过选择性提取页面&#xff0c;你可以更高效地管理和利用PDF文件的内容&#xff0c;无论是…...

godot使用ws

go服务端 package mainimport ("encoding/json""fmt""github.com/gorilla/websocket""net/http" )var upgrader websocket.Upgrader{ReadBufferSize: 1024,WriteBufferSize: 1024, }// 处理函数 func handleWebSocket(w http.Respo…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...