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

构建非苹果硬件的macOS运行环境:Hackintosh长期维护方案

构建非苹果硬件的macOS运行环境&#xff1a;Hackintosh长期维护方案 【免费下载链接】Hackintosh Hackintosh long-term maintenance model EFI and installation tutorial 项目地址: https://gitcode.com/gh_mirrors/ha/Hackintosh 定位项目核心价值 Hackintosh项目作…...

ncmdumpGUI终极指南:解锁你的音乐收藏,告别NCM格式束缚

ncmdumpGUI终极指南&#xff1a;解锁你的音乐收藏&#xff0c;告别NCM格式束缚 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换&#xff0c;Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 你是否曾经遇到过这样的情况&am…...

SDMatte Web服务灰度发布:A/B测试框架搭建、用户行为埋点与转化率效果归因分析

SDMatte Web服务灰度发布&#xff1a;A/B测试框架搭建、用户行为埋点与转化率效果归因分析 1. 项目背景与灰度发布需求 SDMatte作为一款面向高质量图像抠图的AI模型&#xff0c;已在电商、设计等领域得到广泛应用。随着用户量增长和功能迭代&#xff0c;我们需要通过灰度发布…...

终极RippleEffect测试指南:5步确保Android波纹动画质量的完整策略

终极RippleEffect测试指南&#xff1a;5步确保Android波纹动画质量的完整策略 【免费下载链接】RippleEffect Implementation of Ripple effect from Material Design for Android API 9 项目地址: https://gitcode.com/gh_mirrors/ri/RippleEffect RippleEffect是一款为…...

GPON OMCI抓包避坑指南:Wireshark插件版本、芯片指令与实战解析全流程

GPON OMCI抓包避坑指南&#xff1a;Wireshark插件版本、芯片指令与实战解析全流程 在GPON网络运维和研发过程中&#xff0c;OMCI&#xff08;ONU Management and Control Interface&#xff09;协议分析是定位问题的关键手段。但许多工程师在实际操作中常陷入版本兼容性陷阱、芯…...

卡证检测矫正模型效果展示:高清四角点定位+正视角矫正图实拍

卡证检测矫正模型效果展示&#xff1a;高清四角点定位正视角矫正图实拍 你有没有遇到过这样的烦恼&#xff1f;需要上传身份证、驾照或者护照照片时&#xff0c;手机随手一拍&#xff0c;结果照片歪歪扭扭&#xff0c;背景杂乱&#xff0c;关键信息还被手指挡住了。这时候要么…...

YOLOE官版镜像部署指南:从环境配置到实战推理全流程

YOLOE官版镜像部署指南&#xff1a;从环境配置到实战推理全流程 1. 环境准备与快速部署 1.1 系统要求与准备工作 在开始部署YOLOE官版镜像前&#xff0c;请确保您的系统满足以下基本要求&#xff1a; 操作系统&#xff1a;推荐使用Ubuntu 20.04/22.04或CentOS 7/8GPU支持&a…...

Python量化交易入门:利用Baostock API高效获取股票历史数据

1. 为什么选择Baostock获取股票数据&#xff1f; 第一次接触量化交易时&#xff0c;最头疼的就是数据来源问题。市面上的数据接口要么收费昂贵&#xff0c;要么数据质量参差不齐。直到发现了Baostock这个宝藏工具&#xff0c;我的量化研究才真正走上正轨。 Baostock最大的优势在…...

OpenGOAL编译器实战指南:如何构建你自己的Jak游戏

OpenGOAL编译器实战指南&#xff1a;如何构建你自己的Jak游戏 【免费下载链接】jak-project Reviving the language that brought us the Jak & Daxter Series 项目地址: https://gitcode.com/gh_mirrors/ja/jak-project OpenGOAL编译器是一个强大的工具&#xff0c…...

Python 官方下载页面(如 python.org/downloads/)的片段,列出了 Windows 平台下 Python 3.13.11

Python 官方下载页面&#xff08;如 python.org/downloads/&#xff09;的片段&#xff0c;列出了 Windows 平台下 Python 3.13.11&#xff08;发布于 2025 年 12 月 5 日&#xff09;的多种安装包选项。以下是各选项的简要说明&#xff1a; Windows installer (64-bit / 32-b…...