day58 图论章节刷题Part09(dijkstra(堆优化版)、Bellman_ford 算法)
dijkstra(堆优化版)
朴素版的dijkstra解法的时间复杂度为 O(n^2),时间复杂度只和 n(节点数量)有关系。如果n很大的话,可以从边的角度来考虑。因为是稀疏图,从边的角度考虑的话,我们在堆优化算法中最好使用邻接表来存储图,这样不会造成空间的浪费。同时直接遍历边,通过堆(小顶堆)对边进行排序,选择距离源点最近的节点。
时间复杂度:O(ElogE) ,E 为边的数量- logE是小顶堆的时间复杂度
空间复杂度:O(N + E) ,N 为节点的数量,邻接表:O(n+e)、最短距离数组:O(n)、访问标记数组:O(n)、优先队列:O(n)
之前在求top K问题时应用过小顶堆,这里再复习一下。
小顶堆
小顶堆是一种特殊的完全二叉树,其中每个父节点的值都不大于其子节点的值。这种特性使得堆的根节点始终是堆中的最小值,非常适合用于实现优先队列等数据结构。
创建一个优先队列,并进行维护
PriorityQueue priorityQueue = new PriorityQueue<>();
问题应用:
- 求解 Top K 问题:小顶堆可以用于求解 Top K 问题,即从 N 个元素中找出最大的 K 个元素。通过维护一个大小为 K 的小顶堆(当小顶堆中已经有K个元素时,新加入的元素如果大于最小的顶端数据,则将其加入并丢掉顶端数据),可以高效地解决这个问题。
- 合并多个有序数组:通过将每个数组的首个元素放入堆中,每次取出最小值并将其所在数组的下一个元素加入堆中,可以高效地完成合并。
代码实现
import java.util.*;//边的结构:节点和节点间的权重
class Edge{int to,val;Edge(int to,int val){this.to=to;this.val=val;}
}//距离对的结构:节点和节点到源点的距离
class Pair{int first,second;Pair(int first,int second){this.first=first;this.second=second;}
}//重写comparator类作为接口
class MyComparition implements Comparator<Pair>{@Overridepublic int compare(Pair l,Pair r){return Integer.compare(l.second,r.second);}}public class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();List<List<Edge>> grid=new ArrayList<>(n+1);for(int i=0;i<=n;i++){grid.add(new ArrayList<>());}for(int i=0;i<m;i++){int s=scan.nextInt();int t=scan.nextInt();int k=scan.nextInt();grid.get(s).add(new Edge(t,k));}int[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);boolean[] visited=new boolean[n+1];//源点到源点的距离为0minDist[1]=0;PriorityQueue<Pair> pq=new PriorityQueue<>(new MyComparition());pq.add(new Pair(1,0));while(!pq.isEmpty()){Pair cur=pq.poll();if(visited[cur.first]) continue;else visited[cur.first]=true;for(Edge edge:grid.get(cur.first)){if(!visited[edge.to] && minDist[cur.first]+edge.val<minDist[edge.to])minDist[edge.to]=minDist[cur.first]+edge.val;pq.add(new Pair(edge.to,minDist[edge.to]));}}if(minDist[n]!=Integer.MAX_VALUE) System.out.println(minDist[n]);else System.out.println(-1);}
}
Bellman_ford 算法-94. 城市间货物运输 I
本题依然是单源最短路问题,求从节点1 到节点n 的最小费用。 但本题不同之处在于边的权值有负数。
Bellman_ford 算法
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作(n为节点数量),从而求得目标最短路。
“松弛”-如果通过A到B这条边可以获得更短的到达B节点的路径,即如果 minDist[B] > minDist[A] + value,那么我们就更新 minDist[B] = minDist[A] + value。
Bellman_ford算法采用了动态规划的思想,即:将一个问题分解成多个决策阶段,通过状态之间的递归关系最后计算出全局最优解。
对所有边松弛一次,相当于计算起点到达与起点一条边相连的节点的最短距离。所以需要对所有边松弛n-1次才能得到起点到终点的最短距离。
(有一些题目可能不需要n-1次就能找到最短路径,但是n-1次能保证找到各类题目从原点到所有点的最短路径)
时间复杂度: O(N * E) , N为节点数量,E为图中边的数量
空间复杂度: O(N) ,即 minDist 数组所开辟的空间
和dijkstra算法的区别是,dijkstra算法是从源点开始累加最小路径进行推演的;Bellman_ford 算法则相当于不断的累加路径,如果新的路径小于原值就更新。
代码如下:
import java.util.*;
class Edge{int from,to,val;public Edge(int from,int to,int val){this.from=from;this.to=to;this.val=val;}
}class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();List<Edge> edges=new ArrayList<>();for(int i=0;i<m;i++){int from=scan.nextInt();int to=scan.nextInt();int val=scan.nextInt();edges.add(new Edge(from,to,val));}int[] minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;//进行n-1次松弛for(int i=1;i<n;i++){for(Edge edge:edges){if(minDist[edge.from]!=Integer.MAX_VALUE && minDist[edge.from]+edge.val<minDist[edge.to]){minDist[edge.to]=minDist[edge.from]+edge.val;}}}if(minDist[n]==Integer.MAX_VALUE) System.out.println("unconnected");else System.out.println(minDist[n]);}
}
相关文章:
day58 图论章节刷题Part09(dijkstra(堆优化版)、Bellman_ford 算法)
dijkstra(堆优化版) 朴素版的dijkstra解法的时间复杂度为 O(n^2),时间复杂度只和 n(节点数量)有关系。如果n很大的话,可以从边的角度来考虑。因为是稀疏图,从边的角度考虑的话,我们在堆优化算法中最好使用…...
【计网不挂科】计算机网络期末考试——【选择题&填空题&判断题&简述题】试卷(1)
前言 大家好吖,欢迎来到 YY 滴计算机网络 系列 ,热烈欢迎! 本章主要内容面向接触过C的老铁 本博客主要内容,收纳了一部门基本的计算机网络题目,供yy应对期中考试复习。大家可以参考 本章是去答案版本。带答案的版本在下…...
智能出行助手:SpringBoot共享汽车管理平台
1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理共享汽车管理系统的相关信息成为必然。开发…...
【月之暗面kimi-注册/登录安全分析报告】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 …...
Flink实现实时数据处理
代码如下: #!/usr/bin/python # -*- coding: UTF-8 -*-from pyflink.datastream import StreamExecutionEnvironment from pyflink.table import StreamTableEnvironment, EnvironmentSettings, DataTypes# 初始化执行环境 s_env StreamExecutionEnvironment.get_…...
11.9.2024刷华为
文章目录 HJ31 单词倒排HJ32 密码提取语法知识记录 傻逼OD题目又不全又要收费,看毛线,莫名奇妙 HW这叼机构别搁这儿害人得不得? 我觉得我刷完原来的题目 过一遍华为机考的ED卷出处,就行了 HJ31 单词倒排 游戏本做过了好像 HJ3…...
Chromium 中chrome.system.storage扩展接口定义c++
一、chrome.system.storage 您可以使用 chrome.system.storage API 查询存储设备信息,并在连接和分离可移动存储设备时收到通知。 权限 system.storage 类型 EjectDeviceResultCode 枚举 "success" 移除命令成功执行 - 应用可以提示用户移除设备。…...
【Qt聊天室客户端】登录窗口
1. 验证码 具体实现 登录界面中创建验证码图片空间,并添加到布局管理器中 主要功能概述(创建一个verifycodewidget类专门实现验证码操作) 详细代码 // 头文件#ifndef VERIFYCODEWIDGET_H #define VERIFYCODEWIDGET_H#include <QWidget>…...
如何显示模型特征权重占比图【数据分析】
可视化模型的特征权重 1、流程 1、导入库: numpy:用于处理数组和矩阵。 matplotlib.pyplot:用于绘图。 sklearn.datasets:用于加载数据集。 sklearn.ensemble.RandomForestClassifier:用于训练随机森林模型。2、加载数据集: 使用load_iris函数加载Iris数据集。3、训练模…...
Ubuntu24安装MySQL
下载deb包: 先更新系统包: sudo apt update sudo apt update -y下载mysql: wget https://dev.mysql.com/get/mysql-apt-config_0.8.17-1_all.deb 安装deb包: sudo dpkg -i mysql-apt-config_0.8.17-1_all.deb目前mysql还没有正式支持Ubun…...
微服务架构面试内容整理-Eureka
Spring Cloud Netflix 是一个为构建基于 Spring Cloud 的微服务应用提供的解决方案,利用 Netflix 的开源组件来实现常见的分布式系统功能。以下是 Spring Cloud Netflix 的一些主要组件和特点: 服务注册与发现:Eureka 是一个 RESTful 服务,用于注册和发现微服务。服务实例在…...
qt QErrorMessage详解
1、概述 QErrorMessage是Qt框架中用于显示错误消息的一个对话框类。它提供了一个简单的模态对话框,用于向用户显示错误或警告消息。QErrorMessage通常用于应用程序中,当需要向用户报告错误但不希望中断当前操作时。它提供了一个标准的错误消息界面&…...
SpringBoot 将多个Excel打包下载
在Spring Boot应用中,如果你需要将多个Excel文件打包成一个ZIP文件并提供下载,你可以使用一些Java库来帮助完成这个任务。这里我将展示如何使用Apache POI来生成Excel文件,以及使用Java.util.zip来创建ZIP文件,并通过Spring Boot的…...
分页存储小总结
知识点: 什么是分页存储? 将内存空间分为一个个大小相等的分区(比如:每个分区4KB),每个分区就是一个“页框”(页框页帧内存块物理块物理页面)。每个页框有一个编号,即“页框号”(…...
Star-CCM+应用篇之动力电池温度场仿真操作流程与方法
1 动力电池温度场仿真项目 电池包内模组温度分布、电芯温度分布、温升速率、充电时间等。 2 动力电池温度场仿真分析流程图 图1 电池包热流场分析流程 3 动力电池温度场仿真参数需求 类别...
Spring Boot应用开发:从入门到精通
Spring Boot应用开发:从入门到精通 Spring Boot是Spring框架的一个子项目,旨在简化Spring应用的初始搭建和开发过程。通过自动配置和约定大于配置的原则,Spring Boot使开发者能够快速构建独立的、生产级别的Spring应用。本文将深入探讨Sprin…...
【JAVA项目】基于jspm的【医院病历管理系统】
技术简介:采用jsp技术、MySQL等技术实现。 系统简介:通过标签分类管理等方式,实现管理员;个人中心、医院公告管理、用户管理、科室信息管理、医生管理、出诊信息管理、预约时间段管理、预约挂号管理、门诊病历管理、就诊评价管理、…...
Python中的常见配置文件写法
在软件开发过程中,开发者常常需要利用一些固定的参数或常量。对于这些相对恒定且频繁使用的元素,一种常见的做法是将它们集中存储在一个特定的文件中,以避免在多个模块代码中重复定义,从而维护核心代码的清晰度和整洁性。 具体而…...
语义分割实战——基于PSPnet神经网络动物马分割系统源码
第一步:准备数据 动物马分割数据,总共有328张图片,里面的像素值为0和1,所以看起来全部是黑的,不影响使用 第二步:搭建模型 psp模块的样式如下,其psp的核心重点是采用了步长不同,po…...
Python+Appium编写脚本
一、环境配置 1、安装JDK,版本1.8以上 2、安装Python,版本3.x以上,用来解释python 3、安装node.js,版本^14.17.0 || ^16.13.0 || >18.0.0,用来安装Appimu Server 4、安装npm,版本>8,用…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
