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

迪杰斯特拉算法

迪杰斯特拉算法

LeetCode 743. 网络延迟时间

https://blog.csdn.net/xiaoxi_hahaha/article/details/110257368
在这里插入图片描述

import sysdef dijkstra(graph, source):"""dijkstra算法:param graph: 邻接矩阵:param source: 出发点,源点:return:"""# 点的数量n = len(graph)# 源点到各边的初始举例,直接采用邻接矩阵对应行数据即可,注意 sys.maxsize 表示两点之间没有边dis = [sys.maxsize] * ndis[source] = 0# 初始访问过的点只有源点vis = set()# 遍历n-1趟,确定到另外n-1个点的最短路径# 每一趟都可以确定一个点到另外一个点的最短路径while True:# 找到一个距离源点最近的点node = -1for j in range(n):if j not in vis and (node == -1 or dis[j] < dis[node]):node = jif node == -1:break# 用这个最近的点来优化,源点到其他每个点的距离for j in range(n):if dis[j] > dis[node] + graph[node][j]:dis[j] = dis[node] + graph[node][j]vis.add(node)return disgraph = [[0, 5, 2, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize],[5, 0, 1, sys.maxsize, 6, sys.maxsize, sys.maxsize],[2, sys.maxsize, 0, 6, sys.maxsize, 8, sys.maxsize],[sys.maxsize, 1, 6, 0, 1, 2, sys.maxsize],[sys.maxsize, 6, sys.maxsize, 1, 0, sys.maxsize, 7],[sys.maxsize, sys.maxsize, 8, 6, sys.maxsize, 0, 3],[sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 7, 3, 0],
]
print(dijkstra(graph, 0))
# assert dijkstra(graph, 0) == [0, 5, 2, 8, 9, 10, 13]
import heapqdef dijkstra(graph, source):"""使用优先队列优化的 Dijkstra 算法:param graph: 邻接矩阵:param source: 出发点,源点:return: 源点到所有其他顶点的最短路径距离"""# 点的数量n = len(graph)# 源点到各边的初始距离,直接采用邻接矩阵对应行数据即可dis = [sys.maxsize] * ndis[source] = 0  # 源点到自己的距离为0# 优先队列,存储 (距离, 节点) 对priority_queue = [(0, source)]while priority_queue:# 弹出当前距离源点最近的顶点current_distance, current_vertex = heapq.heappop(priority_queue)# 如果弹出的距离大于当前已知的最短距离,则跳过if current_distance > dis[current_vertex]:continue# 遍历当前顶点的所有邻接点for i in range(n):if dis[i] > dis[current_vertex] + graph[current_vertex][i]:dis[i] = dis[current_vertex] + graph[current_vertex][i]heapq.heappush(priority_queue, (dis[i], i))return disprint(dijkstra(graph, 0))

相关文章:

迪杰斯特拉算法

迪杰斯特拉算法 LeetCode 743. 网络延迟时间 https://blog.csdn.net/xiaoxi_hahaha/article/details/110257368 import sysdef dijkstra(graph, source):"""dijkstra算法:param graph: 邻接矩阵:param source: 出发点&#xff0c;源点:return:""&…...

IPsec传输模式与隧道模式的深度解析及应用实例

随着网络安全威胁的日益严峻&#xff0c;IPsec作为网络层安全协议&#xff0c;其传输模式与隧道模式的选择对确保通信安全至关重要。本文旨在深入探讨这两种模式的差异&#xff0c;并通过实际案例展示其应用。 一、传输模式和隧道模式的详细描述 传输模式&#xff1a; 应用场景…...

实现Vue3/Nuxt3 预览excel文件

安装必要的库 npm install xlsx 创建一个组件来处理文件上传和解析&#xff1a; 在src/components 目录下创建一个名为 ExcelPreview.vue 的文件 <template> <div> <input type"file" change"handleFileUpload" /> <table v-if"…...

【AI落地应用实战】HivisionIDPhotos AI证件照制作实践指南

最近在网上发现了一款轻量级的AI证件照制作的项目&#xff0c;名为HivisionIDPhotos。它利用AI模型实现对多种拍照场景的识别、抠图与证件照生成&#xff0c;支持轻量级抠图、多种标准证件照和排版照生成、纯离线或端云推理、美颜等功能。此外&#xff0c;项目还提供了Gradio D…...

php实现sl651水文规约解析

SL651-2014-《水文监测数据通信规约》 1、要素解析说明 39 23 00 00 03 45 0x39查标识符得知为:39H Z 瞬时河道水位、潮位,我们定义为水位 0x23 按照要素标识符的规定,高5bit,低3bit,00100 011 对应的转换为10进制为4与3,也就是水位数据占用4字节,小…...

【Linux】简易版shell

文章目录 shell的基本框架PrintCommandLineGetCommandLineParseCommandLineExecuteCommandInitEnvCheckAndExecBuildCommand代码总览运行效果总结 shell的基本框架 要写一个命令行我们首先要写出基本框架。 打印命令行获取用户输入的命令分析命令执行命令 基本框架的代码&am…...

宝塔Linux面板安装PHP扩展失败报wget: unable to resolve host address ‘download.bt.cn’

一、问题&#xff1a; 当使用宝塔面板安装PHP扩展失败出现如下错误时 Resolving download.bt.cn(download.bt.cn)...failed: Connection timed out. wget: unable toresolve host address download.bt.cn’ 二、解决&#xff1a; 第一步&#xff1a;如下命令执行拿到返回的I…...

问:Redis常见性能问题及解法?

Redis 作为一个高性能的键值存储系统&#xff0c;在实际应用中可能会遇到各种性能问题。本文将探讨 Redis 的常见性能问题&#xff0c;并提供相应的解决建议。主要针对五个关键问题进行讨论&#xff1a;Master 节点的持久化工作、Slave 节点的数据备份、主从复制的网络环境、主…...

Imperva 数据库与安全解决方案

Imperva是网络安全解决方案的专业提供商&#xff0c;能够在云端和本地对业务关键数据和应用程序提供保护。公司成立于 2002 年&#xff0c;拥有稳定的发展和成功历史并于 2014 年实现产值1.64亿美元&#xff0c;公司的3700多位客户及300个合作伙伴分布于全球各地的90多个国家。…...

【JavaScript】之文档对象模型(DOM)详解

JavaScript 的强大之处在于它能够与 HTML 和 CSS 交互&#xff0c;动态地修改网页内容和样式。而实现这一功能的核心就是 DOM&#xff08;文档对象模型&#xff09;。 一、什么是 DOM&#xff1f; DOM 是文档对象模型&#xff08;Document Object Model&#xff09;的缩写。它…...

速盾:cdn域名与ip区别

CDN&#xff08;内容分发网络&#xff09;是一种通过在全球多个服务器上缓存和分发静态资源的网络服务&#xff0c;可以提高网站的访问速度和性能。在使用CDN时&#xff0c;域名与IP地址是两个关键的概念。本文将介绍CDN域名与IP地址的区别和作用。 首先&#xff0c;CDN域名是…...

如何优雅的在页面上嵌入AI-Agent人工智能

前言 IDEA启动&#xff01;大模型的title想必不用我多说了&#xff0c;多少公司想要搭上时代前言技术的快车&#xff0c;感受科技的魅力。现在大模型作为降本增效的强大工具&#xff0c;基本上公司大多人都想要部署开发一把&#xff0c;更多的想要利用到这些模型放到生产中来提…...

如何对LabVIEW软件进行性能评估?

对LabVIEW软件进行性能评估&#xff0c;可以从以下几个方面着手&#xff0c;通过定量与定性分析&#xff0c;全面了解软件在实际应用中的表现。这些评估方法适用于确保LabVIEW程序的运行效率、稳定性和可维护性。 一、响应时间和执行效率 时间戳测量&#xff1a;使用LabVIEW的时…...

动态规划 —— dp问题-按摩师

1. 按摩师 题目链接&#xff1a; 面试题 17.16. 按摩师 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/the-masseuse-lcci/description/ 2. 算法原理 状态表示&#xff1a;以某一个位置为结尾或者以某一个位置为起点 dp[i]表示&#xff1a;选择到i位置…...

SQL 语法学习

在当今数字化的时代&#xff0c;数据的管理和分析变得至关重要。而 SQL&#xff08;Structured Query Language&#xff09;&#xff0c;即结构化查询语言&#xff0c;作为一种用于管理关系型数据库的强大工具&#xff0c;掌握它对于从事数据相关工作的人来说是一项必备技能。在…...

MYSQL---TEST5(Trigger触发器Procedure存储过程综合练习)

触发器Trigger 数据库mydb16_trigger创建 表的创建 goods create table goods( gid char(8) primary key, #商品号 name varchar(10), #商品名 price decimal(8,2), #价格 num int&#xff1b;&#xff09; #数量orders create tabl…...

蓝桥杯 区间移位--二分、枚举

题目 代码 #include <stdio.h> #include <string.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; struct node{ int a,b; }; vector<node> q; bool cmp(node x,node y){ return x.b <…...

Nginx 报错400 Request Header Or Cookie Too Large

错误的原因&#xff1a; 1、可能是你的网络DNS配置错误。 2、由request header过大所引起&#xff0c;request过大&#xff0c;通常是由于cookie中写入了较大的值所引起的。 3、访问太频繁&#xff0c;浏览器的缓存量太大&#xff0c;产生错误。 解决办法&#xff1a; 1、清…...

【Redis】一种常见的Redis分布式锁原理简述

本文主要简述一下基于set命令的Redis分布式锁的原理。 一&#xff0c;a线程持有的锁不要被b线程同时持有→setnx 抢锁的时候&#xff0c;最核心的就是&#xff0c;a线程持有的锁不要被b线程同时持有&#xff0c;放在基于set命令的redis分布式锁中来看&#xff0c;就是“如果锁…...

HOT100_最大子数组和

class Solution {public int maxSubArray(int[] nums) {int[] dp new int[nums.length];int res nums[0];dp[0] nums[0];for(int i 1; i< nums.length; i){dp[i] Math.max(nums[i] ,dp[i-1] nums[i]);res Math.max(res, dp[i]);}return res;} }...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

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

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

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...