迪杰斯特拉算法

迪杰斯特拉算法

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))

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

STL学习-容器适配器

一.stack栈 1.栈的介绍 stack 栈是一种只在一端(栈顶)进行数据插入(入栈)和删除(出栈)的数据结构,它满足后进 先出(LIFO)的特性。 使用push(入栈)将数据放入stack,使用pop(出栈)将元素从容器中移除。 栈的结构如图&#xff1a; 在头文件<stack>中&#xff0c;class st…

【C语言】动态内存开辟

写在前面 C语言中有不少开辟空间的办法&#xff0c;但是在堆上开辟的方法也就只有动态内存开辟&#xff0c;其访问特性与数组相似&#xff0c;但最大区别是数组是开辟在栈上&#xff0c;而动态内存开辟是开辟在堆上的。这篇笔记就让不才娓娓道来。 PS:本篇没有目录实在抱歉CSD…

海的记忆:海滨学院班级回忆录项目

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式&#xff0c;是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示&#xff1a; 图4-1系统工作原理…

【VScode】C/C++多文件夹下、多文件引用、分别编译——仅一个设置【适合新人入手】

【VScode】C/C多文件夹内的多文件引用编译 1、问题2、前提&#xff08;最简环境&#xff09;3、核心&#xff08;关键配置&#xff09;4、成功享用~ 1、问题 在使用 VScode 编写一个简单项目的时候&#xff0c;没有特别配置的情况下&#xff0c;若主文件(.c)引用了自定义的头文…

62 mysql 中 存储引擎MyISAM 中索引的使用

前言 固定数据表 mysql. tables_priv 的表结构创建如下 CREATE TABLE tables_priv (Host char(60) COLLATE utf8_bin NOT NULL DEFAULT ,Db char(64) COLLATE utf8_bin NOT NULL DEFAULT ,User char(32) COLLATE utf8_bin NOT NULL DEFAULT ,Table_name char(64) COLLATE u…

使用buildx构建多架构平台镜像

1. 查看buildx插件信息 比较新的docker-ce版本默认已经集成了buildx插件 [rootdocker ~]# docker buildx version github.com/docker/buildx v0.11.2 9872040 [rootdocker ~]#2. 增加多平台镜像构建支持 通过tonistiigi/binfmt:latest初始化一个基于容器的构建环境&#xff…

数据库基础(3) . Navicat使用

0.下载安装 官网 : https://www.navicat.com.cn/ Navicat 中国 | 支持 MySQL、Redis、MariaDB、MongoDB、SQL Server、SQLite、Oracle 和 PostgreSQL 的数据库管理 1.连接数据库 1.1.连接 1.1.1.点击连接 打开navicat 点击 左上角连接 1.1.2.选择MySQL 弹出配置界面 1.1…

MySQL(上)

一、SQL优化 1、如何定位及优化SQL语句的性能问题&#xff1f;创建的索引有没有被使用到?或者说怎么才可以知道这条语句运行很慢的原因&#xff1f; 对于性能比较低的sql语句定位&#xff0c;最重要的也是最有效的方法其实还是看sql的执行计划&#xff0c;而对于mysql来说&a…

国密SM2 非对称加解密前后端工具

1.依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.21</version></dependency><dependency><groupId>org.bouncycastle</groupId><artifactId>bcpki…

【银河麒麟操作系统】软raid重建速度限制问题分析

了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer.kylinos.cn 文档中心&#xff1a;https://documentkylinos.cn 现象描述 遇到软raid重建速度问题&#xff0c;分…

ssm教室信息管理系统+vue

系统包含&#xff1a;源码论文 所用技术&#xff1a;SpringBootVueSSMMybatisMysql 免费提供给大家参考或者学习&#xff0c;获取源码看文章最下面 需要定制看文章最下面 目 录 目 录 III 1 绪论 1 1.1 研究背景 1 1.2目的和意义 1 1.3 论文结构安排 2 2 相关技术 3 …

去中心化存储:Web3中的数据安全新标准

随着Web3的兴起&#xff0c;去中心化存储逐渐成为数据安全的新标准。传统的中心化存储方式将数据集中保存在少数服务器上&#xff0c;这种模式尽管在早期互联网中被广泛应用&#xff0c;但随着数据量和数据价值的增加&#xff0c;其潜在的安全风险和隐私问题也逐渐暴露。而去中…

Ubuntu 22 安装 Apache Doris 3.0.3 笔记

Ubuntu 22 安装 Apache Doris 3.0.3 笔记 1. 环境准备 Doris 需要 Java 17 作为运行环境&#xff0c;所以首先需要安装 Java 17。 sudo apt-get install openjdk-17-jdk -y sudo update-alternatives --config java在安装 Java 17 后&#xff0c;可以通过 sudo update-alter…

安卓摄像头的详细使用

安卓摄像头的详细使用 一、引言二、权限设置三、打开摄像头四、摄像头的属性设置&#xff08;一&#xff09;预览尺寸&#xff08;二&#xff09;图片格式&#xff08;三&#xff09;对焦模式 五、摄像头预览六、拍照功能七、视频录制 一、引言 在安卓开发中&#xff0c;摄像头…

服务器的配置复杂,租用时该如何选择参数?

对于互联网企业来说&#xff0c;开发一套可以接入互联网的产品&#xff0c;并利用它来盈利是终极目的。但互联网产品必须有服务器才能运行&#xff0c;对于很多公司来说&#xff0c;托管服务器成本太高&#xff0c;而租用服务器才算得上是最好的选择&#xff0c;但面对配置参数…

10min本地安装Qwen1.5-0.5B-Chat

大模型系列文章 本地电脑离线部署大模型 配置&#xff1a;MAC-M1-8GB 10min本地安装Qwen1.5-0.5B-Chat 大模型系列文章前言一、下载Qwen1.5-0.5B-Chat二、构造函数chatBot.py三、启动命令1、放置脚本2、启动命令3、效果图 前言 在人工智能领域&#xff0c;大模型无疑是最炙手…

90%会展主办方都会用的6款数字化工具

在会展行业&#xff0c;数字化转型已成为提升竞争力的关键。面对日益增长的运营成本和收入增长的瓶颈&#xff0c;主办方需要借助数字化工具来实现效率提升和成本控制。 今天介绍几种常见的数字化工具和应用方式。 一、线上展览平台 构建线上展览平台是会展主办方拓展线上销…

弃用 RestTemplate,来了解一下官方推荐的 WebClient !

在 Spring Framework 5.0 及更高版本中&#xff0c;RestTemplate 已被弃用&#xff0c;取而代之的是较新的 WebClient。这意味着虽然 RestTemplate 仍然可用&#xff0c;但鼓励 Spring 开发人员迁移到新项目的 WebClient。 WebClient 优于 RestTemplate 的原因有几个&#xff…

SpringBoot+Thymeleaf电商系统

> 这是一个基于SpringBootThymeleafBootstrap实现的简单电商系统。 > 实现了用户浏览、添加购物车、商品管理等功能&#xff0c;并支持响应式布局。 > 本项目适合JAVA初学者作为入门学习项目 一、部分界面演示 二、技术栈 技术栈中文描述Spring Boot快速开发框架…

02-Dubbo特性及工作原理

02-Dubbo特性及工作原理 Dubbo 的特性 这里说一下 Dubbo 最主要的特性&#xff0c;从这些特性中&#xff0c;就可以看出来我们为什么要选用 Dubbo&#xff0c;也可以将 Dubbo 和 Spring Cloud 进行对比&#xff0c;比如我们搭建一套微服务系统&#xff0c;出于什么考虑选用 Dub…