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

Day60 图论part10

news 来源：原创 2025/7/19 5:37:18

今天大家会感受到 Bellman_ford 算法系列在不同场景下的应用。

建议依然是：一刷的时候，能理解原理，知道Bellman_ford 解决不同场景的问题 ，照着代码随想录能抄下来代码就好，就算达标。 二刷的时候自己尝试独立去写，三刷的时候才能有一定深度理解各个最短路算法。

Bellman_ford 队列优化算法（又名SPFA）

代码随想录

import java.util.*;public class Main{public static void main (String[] args) {//对所有的边松弛n-1次Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();List<List<Edge>> graph = new ArrayList<>(n+1);for(int i = 0; i <= n; i++){graph.add(new ArrayList<>());}for(int i = 0; i < m; i++){int start = scanner.nextInt();int end = scanner.nextInt();int val = scanner.nextInt();graph.get(start).add(new Edge(start, end, val));}int[] minDist = new int[n+1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[1] = 0;Deque<Integer> queue = new ArrayDeque<>();boolean[] isVisited = new boolean[n+1];queue.add(1);isVisited[1] = true;while(!queue.isEmpty()){int start = queue.remove();//取出队列的时候，要取消标记，这样保证有其他路径对该节点进行更新，我们只要保证节点不被重复加入队列即可isVisited[start] = false;for(Edge edge : graph.get(start)){if(minDist[start] + edge.val < minDist[edge.end]){minDist[edge.end] = minDist[start] + edge.val;if(!isVisited[edge.end]){queue.add(edge.end);isVisited[edge.end] = true;}} }}if(minDist[n] == Integer.MAX_VALUE){System.out.println("unconnected");}else{System.out.println(minDist[n]);}}
}class Edge{int start;int end;int val;public Edge(int start, int end, int val){this.start = start;this.end = end;this.val = val;}
}

总结

1.普通的Bellman_ford算法其实是每次都对所有的边都进行一次松弛，但其实但真正有效的松弛，是基于已经计算过的节点在做的松弛。所以我们每次松弛只需要基于上一次松弛更新过的节点，以该节点作为出发节点对连接的边就行。那我们就可以使用队列来记录上一次松弛更新过的节点，把这些节点依次加入到队列里面，然后又取出来处理。

2.队列里面存储的是每条边的起点，我们需要根据这些起点，找到边，所以这样传统的邻接表来存储图是最好的List<List<Edge>> graph = new ArrayList<>(n+1);

3.然后在while循环里面，还有一些地方和之前的处理不一样，我们需要使用isVisited[]数组来判断节点是否在队列里面&#x

Day60 图论part10

今天大家会感受到 Bellman_ford 算法系列在不同场景下的应用。建议依然是：一刷的时候，能理解原理，知道Bellman_ford 解决不同场景的问题，照着代码随想录能抄下来代码就好，就算达标。二刷的时候自己尝试独立去写，三刷的时候才能有一定深度理解各个最短路算法。 Bell…...

编程日记 2025/7/19 5:37:18

「Mac畅玩鸿蒙与硬件50」UI互动应用篇27 - 水果掉落小游戏

本篇教程将带你实现一个水果掉落小游戏，掌握基本的动态交互逻辑和鸿蒙组件的使用，进一步了解事件处理与状态管理。关键词 UI互动应用水果掉落状态管理动态交互游戏开发一、功能说明水果掉落小游戏包含以下交互功能： 随机生成水果&#…...

编程日记 2025/7/19 5:02:43

Java [后端] 开发日常记录（1）

目录 1、常用的注解 2、对字符串的处理 3、对JSON串的处理 -- The End -- 详细如下： 1、常用的注解若返回的字段中有NUll，则不返回 JsonInclude(value JsonInclude.Include.NON_NULL) //在实体类中添加这个注解 JsonInclude(JsonInclude.Include.NON…...

编程日记 2025/7/19 4:41:27

【Spring】Spring DI(依赖注入)详解——自动装配——手动装配与自动装配的区别

在spring开发中，依赖注入（Dependency Injection，DI）是实现松耦合和高内聚设计的重要模式。它使得对象的创建和管理与其依赖关系分离，从而提高了代码的可维护性、可测试性和灵活性。Spring框架通过IoC（控制反…...

编程日记 2025/7/19 4:40:26

科普时刻 | 3D-IC设计：芯片集成的创新方法

技术的进步推动了日益复杂和密集的集成电路（IC）不断发展。为了满足对高性能和节能设备不断增长的需求，行业已转向3D-IC设计。3D-IC在消费类电子产品、电信、计算和汽车等众多行业都有广泛的应用。什么是3D-IC技术？ 3D-IC技术是…...

编程日记 2025/7/18 15:53:28

自研国产零依赖前端UI框架实战009 数组相关方法和新增修改功能实现

前言我们已经实现了用户管理相关的页面,为此也封装了很多的组件. 按照原本的计划, 我们还要封装一些常用的操作数组的方法. 将元素插入数组的任意位置 // 将元素插入数组的指定位置 const insert (arr, // 数组element, // 元素index, // 指定索引 ) > {if (index &l…...

编程日记 2025/7/19 5:33:12

DBeaver连接OceanBase数据库

OceanBase分Oracle租户模式和mysql租户模式，一般企业常用的是Oracle住户模式，下面介绍下DBeaver连接OceanBase Oracle租户模式下的数据库 DBeaver 标签栏 - 数据库 - 驱动管理器新建 OB 驱动填写如下参数一般拿到的ob连接信息如下 Oceanbase数据库服…...

编程日记 2025/7/19 5:24:47

活动预告 |【Part1】Microsoft Azure 在线技术公开课：基础知识

课程介绍参加“Azure 在线技术公开课：基础知识”活动，培养有助于创造新的技术可能性的技能并探索基础云概念。参加我们举办的本次免费培训活动，扩充自身的云模型和云服务类型知识。你还可以查看以计算、网络和存储为核心的 Azure 服务。活…...

编程日记 2025/7/13 8:06:40

傲雷亮相2024中国时尚体育季（珠海站），展现户外移动照明风采

2024年12月28-29日，2024中国时尚体育季（珠海站）国家级轮滑比赛在珠海金山体育公园成功举办。作为户外创新型移动照明领域的领导品牌，傲雷受邀参加了本次珠海金湾运动生活嘉年华的展览单元，与众多户外运动品牌同台展示。…...

编程日记 2025/7/19 5:37:18

LangChain4j与Elasticsearch：构建高效的语义嵌入存储

LangChain4j与Elasticsearch：构建高效的语义嵌入存储一、LangChain4j与Elasticsearch集成概述 1.1 LangChain4j简介 LangChain4j是一个为Java开发者设计的开源库，旨在简化大型语言模型（LLM）在Java应用程序中的集成。它提供了与…...

编程日记 2025/7/19 5:10:27

IO Virtualization with Virtio.part 1 [十二]

久等了各位！ 本篇开始讲解 IO 虚拟化中的 virtio，我会以 Linux 的 IIC 驱动为例，从 IIC 驱动的非虚拟化实现，到 IIC 驱动的半虚拟化实现，再到最后 X-Hyper 中如何通过 virtio 来实现前后端联系，一步步把 v…...

编程日记 2025/7/19 4:57:37

单元测试4.0+思路总结

Jmockit使用笔记_增加代码覆盖率_覆盖try catch_使用new MockUp私有方法-CSDN博客一般使用new MockUp模拟被测试代码中的私有方法(常用） 使用new Expetations模拟被测试代码中的方法?...

编程日记 2025/7/19 5:36:17

微信小程序中遇到过的问题

记录微信小程序中遇到的问题（持续更新ing） 问题描述：1. WXML中无法直接调用JavaScript方法。2. css中无法直接引用背景图片。3. 关于右上角胶囊按钮。4. 数据绑定问题。5. 事件处理问题。6. 关于movable-view组件的问题7. 关于设置宽度后设置…...

编程日记 2025/7/19 5:15:36

气象数据Grib及Python绘图

文章较长，却将所有常见的气象数据类型进行了详细的介绍，对各种方法的优劣势进行了详细分析，相信对于阅读者来说会有一定程度的帮助目录 GRIB 数据格式简介使用Python处理Grib文件法1：使用pygrib库法2：使用cf…...

编程日记 2025/7/14 19:07:10

Vue el-data-picker选中开始时间，结束时间自动加半小时

效果思路查阅elemnet plus官网，日期时间选择器type"datetimerange"这个选中开始时间并没有对应事件会被触发，因此思路更换成type"datetime"的两个组成一起可以通过监听开始时间v-model的值变化更新结束时间的值。代码日期时间…...

编程日记 2025/7/19 4:52:53

通过Homebrew安装 - 国内下载地址 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"安装nvm brew install nvm 配置nvm环境变量 export NVM_DIR“$HOME/.nvm” [ -s “/usr/local/opt/nvm/nvm.sh” ] && . “/usr/…...

编程日记 2025/7/19 4:41:26

模型并行、数据并行、流水线并行以及混合并行的适用场景、优劣

模型并行、数据并行、流水线并行以及混合并行的适用场景、优劣数据并行适用场景：适用于模型规模相对较小，能够在单个计算设备（如 GPU）上完整运行，但训练数据量巨大的情况。例如在大规模图像分类任务中，常见的卷积神经网络模型（如 ResNet、VGG 等）在处理大规模图像数据…...

编程日记 2025/7/19 5:18:41

【容器化技术 Docker 与微服务部署】详解

容器化技术 Docker 与微服务部署一、容器化技术概述 （一）概念容器化技术是一种操作系统级别的虚拟化方法，它允许将应用程序及其依赖项（如运行时环境、系统工具、库等）打包成一个独立的、可移植的单元，这…...

编程日记 2025/7/19 5:20:43

MySQL——数据类型

一、常见的数据类型及分类其中上述的数值类型包含了整形和浮点型，文本、二进制类型主要是字符串类型。整数类型（Integer Types）： TINYINT：范围为-128到127或0到255（无符号），用于…...

编程日记 2025/7/18 23:08:12

基于傅立叶神经网络（FNN）与物理信息神经网络（PINN）求解泊松方程(附Pytorch源代码)

基于傅立叶神经网络（FNN）与物理信息神经网络（PINN）求解泊松方程一、引言偏微分方程（Partial Differential Equation, PDE）在科学与工程领域有着广泛的应用。传统数值方法（如有限差分法、有限元法）在求解这类问题时，尽管已经非常成熟，但随着问题复杂度的增加，其计…...

编程日记 2025/7/19 5:04:33

FastExcel：超越EasyExcel的新一代Excel处理工具

简介 FastExcel是由原EasyExcel作者在阿里巴巴宣布停止维护EasyExcel之后推出的升级版框架。它继承了EasyExcel的所有优点，并且在性能和功能上进行了显著的提升和创新。 FastExcel的特点高性能读写：FastExcel专注于性能优化，能够高效处理…...

编程日记 2025/7/19 5:01:21

项目优化性能监控

目录 1. 性能平台搭建 1.1 影响性能的关键要素 1.2 压力测试 1.3 压力测试指标 1.4 Jmeter 1.5 Jmeter常用插件 1.6 性能关键指标 1.7 服务器硬件资源监控 1.8 系统负载:load average 1.9 搭建压测监控平台 1.10 梯度压测：分析接口性能瓶颈 2. 项目优化…...

编程日记 2025/7/19 5:15:35

linux装git

前言以 deepin 深度系统为例，安装命令行版 Git 非常简单。安装注意：需要输入账号密码，否则无法进行。打开终端，执行如下命令即可。 sudo apt-get install git成功如下图所示，输入 git ，命令识别即…...

编程日记 2025/7/19 5:12:21

2024 年度总结

时光荏苒，2024 年即将画上句号，回顾这一年的写博历程，有付出、有收获、有成长，也有诸多值得回味与反思的瞬间。一、内容创作主题涉猎：这一年，我致力于探索多样化的主题，以满足不同读者群体的…...

编程日记 2025/7/19 5:32:09

实验八指针2

7-1 利用指针返回多个函数值分数 30 全屏浏览切换布局作者陈晓梅单位广东外语外贸大学读入n个整数，调用max_min()函数求这n个数中的最大值和最小值。输入格式: 输入有两行： 第一行是n值； 第二行是n个数。输出格式: 输出最大…...

编程日记 2025/7/19 5:11:25

python修改ppt中的文字部分及插入图片

批量修改ppt中的某个模块，或者批量制作奖状等场景会用到； import os import pandas as pd from pptx import Presentation from pptx.util import Inchesfilepath/Users/kangyongqing/Documents/kangyq/202303/分析模版/批量制作/file1时段预警_副本.pp…...

编程日记 2025/7/13 11:08:13

C进阶-字符串与内存函数介绍（另加2道典型面试题）

满意的话，记得一键三连哦！ 我们先看2道面试题第一道： 我们画图理解： pa，先使用再，pa开始指向a【0】，之后pa向下移动一位，再解引用，指向a【1】，a【1】又指向…...

编程日记 2025/7/17 12:10:09

Github - 如何提交一个带有“verified”标识的commit

Github - 如何提交一个带有“verified”标识的commit 前言(Why) 今天在Github上浏览某项目的commit记录的时候发现，有的commit记录带有verified绿色标识，有的带有橘色的Unverified标识，还有的什么都不显示。既然我是根正苗红的作者(bushi)…...

编程日记 2025/7/15 13:43:14

充电桩语音提示IC方案-支持OTA远程更换语音WT2003H让充电更智能

随着新能源汽车产业的蓬勃发展，充电桩作为电动汽车能量补给的关键设施，其智能化、人性化设计日益成为行业关注的焦点。在这一背景下，WT2003H4-16S语音芯片方案的推出，无疑为充电桩的智能化升级注入了新的活力。该方案不仅提升了充…...

编程日记 2025/7/17 7:58:29

[2474].第04节：Activiti官方画流程图方式

我的后端学习大纲 Activiti大纲 1.安装位置： 2.启动：...

编程日记 2025/7/2 11:51:26

开源的Vue低代码表单设计器 form-create-designer v3.2.9 版本发布，新增10多种功能

form-create-designer 是一款开源的低代码表单设计器，通过数据驱动表单渲染。可以通过拖拽的方式快速创建表单，提高开发者对表单的开发效率，节省开发者的时间。并广泛应用于在政务系统、OA系统、ERP系统、电商系统、流程管理等领域。项目采…...

编程日记 2025/7/15 1:05:57

0042__【小沐学OpenGL】Ubuntu环境下glfw的安装和使用

【小沐学OpenGL】Ubuntu环境下glfw的安装和使用_ubuntu glfw-CSDN博客 OpenGL 打开绘制窗口学习笔记_glfwmakecontextcurrent-CSDN博客...

编程日记 2025/7/17 19:45:45

第一节：电路连接【51单片机+A4988+步进电机教程】

摘要：本节介绍如何搭建一个51单片机A4988步进电机控制电路，所用材料均为常见的模块，简单高效的方式搭建起硬件环境一、硬件清单 ①51单片机最小控制模块 ②开关电源 ③A4988模块转接座 ④二相四线步进电机 ⑤电线若干二、接线三、A49…...

编程日记 2025/7/18 22:28:04

k8s 部署meilisearch UI

https://github.com/riccox/meilisearch-ui 拉取镜像 sudo docker pull riccoxie/meilisearch-ui:latestk8s 部署 apiVersion: v1 kind: Service metadata:name: meilisearch-uinamespace: meilisearch spec:type: NodePortselector:app: meilisearch-uiports:- port: 24900…...

编程日记 2025/7/15 12:39:43

Bellman_ford 队列优化算法（又名SPFA）

相关文章：