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,用…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
