两点间最短距离 - Dijkstra
一、汇总
算法 | 场景 | 说明 | 参考 |
BFS | 树 无权图的搜索 | 标准BFS默认搜索一条最短路径 改造后可以输出所有最短路径 | https://blog.csdn.net/m0_37145844/article/details/144534202 |
DFS | 走迷宫 | 主要利用回溯算法思想,不保证最短路径 | https://blog.csdn.net/m0_37145844/article/details/144534202 |
Dijkstra | 带权图最短路径的经典解法 | 主要利用贪心思想,其中在u打印路径时候包含递归,回溯等思想 | 本篇讲解 |
二、Dijkstra 原理
借助java工具类:PriorityQueue 默认内部元素强制根据指定规则进行自然排序的的小顶堆,每次选择下层节点到起点开始算的最小权值的节点作为当前节点,进行向外的下一个层级的探索,最终让所有节点都保存了,此节点从开始节点的最小权重值及其最短路径的父节点。
三、Dijkstra 代码实现-Java版本
有必要讲解一下代码结构:
- 内部类的使用
- 体现更强的封装性,结构体仅供外部类使用,不对外暴露。
- 外部类可以直接调用内部类,简化代码。
- 内部类也可以直接使用外部类的成员变量,此例子中暂无体现。
- 优先级队列的使用
- 比较器的构造。
- 因为每次向外层探索时候,都会加入下一层到开始节点权重总和最小的节点,此数据结构强制进行排序,序列化为一个小顶堆。这也是提升此算法性能的关键设计。
- 默认为小顶堆。
- 距离Map和路径反向记录Map,都体现了算法设计的技巧。
- 尤其在打印路径时候,最终用递归思想。
package algo.backtrace.Dijkstra.weiwei;import java.util.*;public class Dijkstra {class Grap {// 带权重的无向图表示,邻接矩阵表示Map<Integer, List<Edag>> adjList;Grap() {adjList = new HashMap<>();}// 添加边public void addEdag(int start, int des, int weight) {adjList.putIfAbsent(start, new ArrayList<>());adjList.putIfAbsent(des, new ArrayList<>());adjList.get(start).add(new Edag(des, weight));adjList.get(des).add(new Edag(start, weight));}// 获取一个顶点的所有边public List<Edag> getEdags(int node) {return adjList.getOrDefault(node, new ArrayList<>());}// 获取所有顶点public Set<Integer> getAllNodes() {return adjList.keySet();}}// 描述边class Edag{int des;int weight;Edag(int des, int weight) {this.des = des;this.weight = weight;}}public Map<Integer, Integer> dijkstra(Grap grap, Integer start) {// 定义工具PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));Map<Integer, Integer> dist = new HashMap<>();Map<Integer, Integer> prev = new HashMap<>();// 初始化参数for (Integer node : grap.getAllNodes()) {dist.put(node, Integer.MAX_VALUE);prev.put(node, -1);}dist.put(start, 0);pq.offer(new int[]{start, 0});while (!pq.isEmpty()) {int[] poll = pq.poll();int currNode = poll[0];int currWeight = poll[1];if (currWeight > dist.get(currNode)) {continue;}for (Edag edag : grap.getEdags(currNode)) {int newDist = currWeight + edag.weight;if (newDist < dist.get(edag.des)) {dist.put(edag.des, newDist);prev.put(edag.des, currNode);pq.offer(new int[]{edag.des, newDist});}}}System.out.println("dist:" + dist);System.out.println("prev:" + prev);return prev;}public void printTrace(Map<Integer, Integer> prevMap, int traget, List<Integer> trace) {if (prevMap.get(traget) == -1) {return;}traget = prevMap.get(traget);printTrace(prevMap, traget, trace);trace.add(traget);}public void main(String[] args) {Grap grap = new Grap();grap.addEdag(0,1,4);grap.addEdag(0,2,1);grap.addEdag(1,3,2);grap.addEdag(2,3,8);grap.addEdag(2,4,3);grap.addEdag(4,5,2);grap.addEdag(3,5,1);Dijkstra dijkstra = new Dijkstra();Map<Integer, Integer> prevMap = dijkstra.dijkstra(grap, 0);List<Integer> list = new ArrayList<>();dijkstra.printTrace(prevMap, 5, list);System.out.println(list);}
}// 输出
// dist:{0=0, 1=4, 2=1, 3=6, 4=4, 5=6}
// prev:{0=-1, 1=0, 2=0, 3=1, 4=2, 5=4}
// [0, 2, 4] 瑕疵之处是traget 没有打印出,无伤大雅。
相关文章:
两点间最短距离 - Dijkstra
一、汇总 算法场景说明参考BFS 树 无权图的搜索 标准BFS默认搜索一条最短路径 改造后可以输出所有最短路径 https://blog.csdn.net/m0_37145844/article/details/144534202DFS走迷宫主要利用回溯算法思想,不保证最短路径https://blog.csdn.net/m0_37145844/articl…...
0002__GPU
国内GPU公司主要包括以下几家: 摩尔线程:摩尔线程被誉为“中国版英伟达”,成立于2019年,由前英伟达全球副总裁张建中创立。该公司已获得425项授权专利,计划上市,目标估值高达1500亿元。摩尔线程的技术…...
StarRocks 排查单副本表
文章目录 StarRocks 排查单副本表方式1 查询元数据,检查分区级的副本数方式2 SHOW PARTITIONS命令查看 ReplicationNum修改副本数命令 StarRocks 排查单副本表 方式1 查询元数据,检查分区级的副本数 # 方式一 查询元数据,检查分区级的副本数…...
基于字节大模型的论文翻译(含免费源码)
基于字节大模型的论文翻译 源代码: 👏 star ✨ https://github.com/boots-coder/LLM-application 展示 项目简介 本项目是一个基于大语言模型(Large Language Model, LLM)的论文阅读与翻译辅助工具。它通过用户界面(…...
【原生js案例】ajax的简易封装实现后端数据交互
ajax是前端与后端数据库进行交互的最基础的工具,第三方的工具库比如jquery,axios都有对ajax进行第二次的封装,fecth是浏览器原生自带的功能,但是它与ajax还是有区别的,总结如下: ajax与fetch对比 实现效果 代码实现 …...
uniapp Native.js 调用安卓arr原生service
有问题,文中的内容不正确 最近搞了个uni小项目,一个定制的小平板,带一个nfc设备,厂家只给了一套安卓原生demo,头一次玩原生安卓,废了好半天劲打出来arr包,想镶进uniapp里,网上查了好…...
关于画火山图(by ggplot2)的一些总结和经验
愿武艺晴小朋友一定得每天都开心! 文献中常用经典的火山图,是展示差异表达基因的利器。每次测完转录组,做实验组和对照组的比较后,都会用到。 我自己也画了不算太多也不算太少的次数。然后最近画的时候忽然间意识到这个可视化方法我经常用,却没系统的整理过,一些tips散…...
组装一台电脑需要哪些硬件设备?点击了解
组装一台电脑是一个既有趣又实用的过程,我们可以根据自己的需求和预算来定制一台完全符合个人使用习惯的计算机。 一、核心部件 1、中央处理器(CPU) CPU是计算机的“大脑”,负责执行各种计算任务。它的性能直接影响到计算机的运…...
Mac M1使用pip3安装报错
1. Mac系统使用pip3安装组件的时候报”外部管理环境”错误: error: externally-managed-environment 2.解决办法 去掉这个提示 1、先查看当前python版本: python3 --version 2、查找EXTERNALLY-MANAGED 文件的位置(根据自己当前使用的pytho…...
在Linux系统安装配置 MySQL 和 hive,hive配置为远程模式
前提:已安装配置好了Hadoop环境,因为hive的底层是Hadoop 1 Mysql安装 搜索Centos7自带的mariadb rpm -qa|grep mariadb 卸载mariadb rpm -e mariadb-libs-5.5.64-1.el7.x86_64 --nodeps 再搜索一次看看是否还存在 rpm -qa|grep mariadb 安装mysql 创…...
亚信安全与方天股份达成战略合作,双向奔赴助力数字化转型
近日,亚信安全科技股份有限公司(以下简称“亚信安全”)正式与青岛方天科技股份有限公司(以下简称“方天股份”)签订合作框架协议。双方强强携手,在网络安全运营平台共建、信息化项目安全支撑、政企市场拓展…...
ubuntu镜像开荒ssh
直接unminimized deprecated me ubuntu 安装 ssh,用 service 启动 4o 在 Ubuntu 上安装并启动 SSH 服务,你可以按照以下步骤进行操作: 更新软件包列表: 首先,确保你的软件包列表是最新的。打开终端并运行以下命令&…...
前端yarn工具打包时网络连接问题排查与解决
最近线上前端打包时提示 “There appears to be trouble with your network connection”,以此文档记录下排查过程。 前端打包方式 docker启动临时容器打包,命令如下 docker run --rm -w /app -v pwd:/app alpine-node-common:v16.20-pro sh -c "…...
CCF-GESP 等级考试 C++ 真题解析目录
GESP C 一级 序号日期真题解析链接12023.03CCF-GESP 等级考试 2023年3月认证C一级真题解析22023.06CCF-GESP 等级考试 2023年6月认证C一级真题解析32023.09[CCF-GESP 等级考试 2023年9月认证C一级真题解析]42023.12[CCF-GESP 等级考试 2023年12月认证C一级真题解析]52024.03[C…...
如何使用 WebAssembly 扩展后端应用
1. WebAssembly 简介 随着互联网的发展,越来越多的应用借助 Javascript 转到了 Web 端,但人们也发现,随着移动互联网的兴起,需要把大量的应用迁移到手机端,随着手端的应用逻辑越来越复杂,Javascript 的解析…...
从DINO到DINOv2——自监督视觉Transformer的升级改进之路(基于ViT)
前言 之所以关注到DINOV2,原因在于我解读多个具身机器人模型时——发现他们的视觉基座都用的DINOV2,比如 rekepOpen-TeleVisionOpenVLACogACTOKAMI 不过,实话讲,DINO论文的可读性是真的不高,使得本次解读不易..总之…...
CCF-GESP 等级考试 2024年12月认证C++七级真题解析
2024年12月真题 一、单选题(每题2分,共30分) 正确答案:D 解析:考察字符类型和ASCII码值。 字符类型参与运算,是它所对应的ASCII码值在参与运算,运算结果为整数值。小写字母 b 的ASCII码为98&am…...
Qt之串口设计-线程实现(十二)
Qt开发 系列文章 - Serial-port(十二) 目录 前言 一、SerialPort 二、实现方式 1.创建类 2.相关功能函数 3.用户使用 4.效果演示 5.拓展应用-实时刷新 总结 前言 Qt作为一个跨平台的应用程序开发框架,在串口编程方面提供了方便易用…...
20241217使用M6000显卡在WIN10下跑whisper来识别中英文字幕
20241217使用M6000显卡在WIN10下跑whisper来识别中英文字幕 2024/12/17 17:21 缘起,最近需要识别法国电影《地下铁》的法语字幕,使用 字幕小工具V1.2【whisper套壳/GUI封装了】 无效。 那就是直接使用最原始的whisper来干了。 当你重装WIN10的时候&#…...
基于 uniapp 开发 android 播放 webrtc 流
一、播放rtsp协议流 如果 webrtc 流以 rtsp 协议返回,流地址如:rtsp://127.0.0.1:5115/session.mpg,uniapp的 <video> 编译到android上直接就能播放,但通常会有2-3秒的延迟。 二、播放webrtc协议流 如果 webrtc 流以 webrt…...
Java反射学习(3)(“反射“机制获取成员变量及详细信息(Field类))
目录 一、基本引言。 (1)基本内容回顾。 (2)本篇博客的核心内容-基本介绍。 二、Java中使用"反射"机制获取成员变量及内部的详细信息。 (1)"反射"机制获取成员变量及详细信息的基本概念…...
Flutter组件————AppBar
AppBar 是 Flutter 中用于创建应用程序顶部栏的组件,它遵循 Material Design 规范。 参数: 参数名称类型描述titleWidget设置 AppBar 中的标题文本或自定义标题小部件。automaticallyImplyLeadingbool决定是否自动添加返回按钮(如果页面不是…...
LabVIEW在电液比例控制与伺服控制中的应用
LabVIEW作为一种图形化编程环境,广泛应用于各类控制系统中,包括电液比例控制和伺服控制领域。在这些高精度、高动态要求的控制系统中,LabVIEW的优势尤为突出。以下从多个角度探讨其应用与优势: 1. 灵活的控制架构 LabVIEW为电…...
Jenkins
1.安装 需要先安装jdk11 yum install -y java-11 yum localinstall -y jenkins-2.361.4-1.1.noarch.rpm 启动服务 systemctl enable --now jenkins.service 开始安装 进入下一步,关掉即可 下一步,点击开始使用Jenkins 2.插件的安装 1.方式一&…...
Sigrity System Explorer Snip Via Pattern From Layout模式从其它设计中截取过孔模型和仿真分析操作指导
Sigrity System Explorer Snip Via Pattern From Layout模式从其它设计中截取过孔模型和仿真分析操作指导 Sigrity System Explorer Snip Via Pattern From Layout模式支持从其它设计中截取过孔模型用于仿真分析,同样以差分模板为例 具体操作如下 双击打开System Explorer软件…...
Redux使用教程
Redux使用教程 一、安装依赖 安装ReduxToolkit、react-redux,命令行输入 npm i reduxjs/toolkit react-redux二、创建目录结构 创建标准的store目录结构,当然这一步不是必须的 ① 在src下创建store文件夹 ② 在store文件夹中创建一个modules文…...
gpu硬件架构
1.简介 NVIDIA在视觉计算和人工智能(AI)领域处于领先地位;其旗舰GPU已成为解决包括高性能计算和人工智能在内的各个领域复杂计算挑战所不可或缺的。虽然它们的规格经常被讨论,但很难掌握各种组件的清晰完整的图景。 这些GPU的高性…...
volatility2工具的使用vol2工具篇
vol2工具 命令格式:vol.py -f [image] --profile[profile] [plugin] 1、查看系统的操作版本,系统镜像信息 2.查看用户名密码信息,当前操作系统中的password hash,例如SAM文件内容 3.从注册表提取LSA密钥信息(已解密&…...
LeetCode:104.二叉树的最大深度
跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的! 代码随想录 LeetCode:104.二叉树的最大深度 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节…...
【游戏设计原理】19 - 得益
一、学习与分析 核心概念总结: 得益(Payoff):玩家在游戏中通过决策获得的产出,包括正面和负面。它可以以分数、等级、货币等形式体现。玩家差异:不同玩家追求不同类型的回报,有些人重视分数或…...
简单配置,全面保护:HZERO审计服务让安全触手可及
HZERO技术平台,凭借多年企业资源管理实施经验,深入理解企业痛点,为您提供了一套高效易用的审计解决方案。这套方案旨在帮助您轻松应对企业开发中的审计挑战,确保业务流程的合规性和透明度。 接下来,我将为大家详细介绍…...
day5,数据结构,单向,双向,循环链表
1】思维导图 2】完成单向循环链表的所有操作 【创建、判空、尾插、遍历、尾删、销毁】 创建: LooplinkPtr caerte() {LooplinkPtr h(LooplinkPtr)malloc(sizeof(Looplink));if(NULLh){printf("创建失败\n");return NULL;}h->len0;h->data0;h->…...
构建高性能异步任务引擎:FastAPI + Celery + Redis
在现代应用开发中,异步任务处理是一个常见的需求。无论是数据处理、图像生成,还是复杂的计算任务,异步执行都能显著提升系统的响应速度和吞吐量。今天,我们将通过一个实际项目,探索如何使用 FastAPI、Celery 和 Redis …...
Linux 中检查 Apache Web Server (httpd) 正常运行时间的 4 种方法
注:机翻,未校。 4 Ways To Check Uptime of Apache Web Server (httpd) on Linux November 28, 2019 by Magesh Maruthamuthu We all know about the purpose of uptime command in Linux. 我们都知道 Linux 中 uptime 命令的目的。 It is used to c…...
简易CPU设计入门:内存初始化文件(三)
项目代码下载 请大家首先准备好本项目所用的源代码。如果已经下载了,那就不用重复下载了。如果还没有下载,那么,请大家点击下方链接,来了解下载本项目的CPU源代码的方法。 下载本项目代码 准备好了项目源代码以后,我…...
深度解析Meta最新发布的虚拟试穿技术:一键试衣的革命性进展
随着电子商务的发展,消费者对在线购物体验的要求越来越高。为了满足这一需求,Meta最近发布了一款面向电商人群的一键试衣工具,它不仅能够实现精确控制人物的外观(虚拟试衣)和姿态(姿态迁移),还能保持参考图像中的细节纹理特征,避免失真。这项技术通过引入基于注意力机…...
Apache Solr RCE(CVE-2017-12629)--vulhub
Apache Solr 远程命令执行漏洞(CVE-2017-12629) Apache Solr 是一个开源的搜索服务器。Solr 使用 Java 语言开发,主要基于 HTTP 和 Apache Lucene 实现。原理大致是文档通过Http利用XML加到一个搜索集合中。查询该集合也是通过 http收到一个…...
使用二分查找法找出给定点距离给定点集合距离最近的点
1、场景描述 给定点Point A (x,y)和 直线点集合 Points [(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)......],计算出集合中距离点A最近的一个点 (如果集合中的两个点距离A点最近且相等,则只取其中一个) 2、代码&#x…...
凯酷全科技抖音电商服务的卓越践行者
在数字经济蓬勃发展的今天,电子商务已成为企业增长的新引擎。随着短视频平台的崛起,抖音作为全球领先的短视频社交平台,不仅改变了人们的娱乐方式,也为品牌和商家提供了全新的营销渠道。厦门凯酷全科技有限公司(以下简…...
复盘:“辩论赛”复盘
这个小活动整个下来,我是按照“策划-执行-总结-复盘“这个顺序来过的; 在策划上: 首先,针对这个论题,我其实很清楚有很多问题,比如引起逆反心理,没想到还有不少人参与。 其次,针对这…...
SSD目标检测算法
SSD(Single Shot MultiBox Detector)是一种基于深度学习的目标检测算法,它结合了高效的检测策略和准确的检测结果。相比于传统的目标检测算法,SSD能够在保持较高准确性的同时快速地进行目标检测。 SSD算法的主要特点包括以下几个…...
MyBatis通过注解配置执行SQL语句原理源码分析
文章目录 前置准备流程简要分析配置文件解析加载 Mapper 接口MapperAnnotationBuilder解析接口方法注解parseStatement 方法详解MapperBuilderAssistant 前置准备 创建一个mybatis-config.xml文件,配置mapper接口 <mappers><!--注解配置--><mapper…...
12_HTML5 Video(视频) --[HTML5 API 学习之旅]
HTML5 引入了 <video> 标签,使得在网页中嵌入和控制视频变得非常简单。<video> 元素允许你直接在 HTML 中指定视频文件,并提供了多种属性和方法来控制视频的播放、暂停、音量等。 基本用法 HTML5 的 <video> 标签让嵌入和控制视频变…...
JaxaFx学习(三)
目录: (1)JavaFx MVVM架构实现 (2)javaFX知识点 (3)JavaFx的MVC架构 (4)JavaFx事件处理机制 (5)多窗体编程 (6)数据…...
视频点播系统|Java|SSM|VUE| 前后端分离
【技术栈】 1⃣️:架构: B/S、MVC 2⃣️:系统环境:Windowsh/Mac 3⃣️:开发环境:IDEA、JDK1.8、Maven、Mysql5.7 4⃣️:技术栈:Java、Mysql、SSM、Mybatis-Plus、VUE、jquery,html 5⃣️数据库可…...
Springboot 学习 之 logback-spring.xml 日志压缩 .tmp 临时文件问题
文章目录 前言功能简述1. 自定义日志文件名2. 归档规则 && 压缩2.1. 归档配置2.2. 归档压缩2.3. 日志格式 && 编码 现象原因解决办法 前言 在 Springboot 应用中,默认使用 logback-spring.xml 配置日志相关 功能简述 1. 自定义日志文件名 <fi…...
智慧工地整体解决方案
智慧工地背景与需求 智慧工地解决方案的提出,源于建筑行业面临的诸多挑战。安全事故频发、环保体系不健全、建筑信息化水平低以及施工现场管理难度大等问题,迫切需要通过智能化手段来提升工地管理的效率与安全性。智慧工地利用现代信息技术,…...
【读书打卡版】【读书笔记】半小时漫画中国地理3
一 如果全中国是个班级,江南五省各不同 继续跟随长江的脚步,认识坐在长江中下游平原上的省份:安徽、江苏、江西、浙江、上海。他们同属于一个美丽又富饶的大区——江南。 那么问题来了,一提到江南,你会想到什么&#…...
harmony UI组件学习(1)
Image 图片组件 string格式,通常用来加载网络图片,需要申请网络访问权限:ohos.permission.INTERNET Image(https://xxx.png) PixelMap格式,可以加载像素图,常用在图片编辑中 Image(pixelMapobject) Resource格式,加…...
ECharts热力图-笛卡尔坐标系上的热力图,附视频讲解与代码下载
引言: 热力图(Heatmap)是一种数据可视化技术,它通过颜色的深浅变化来表示数据在不同区域的分布密集程度。在二维平面上,热力图将数据值映射为颜色,通常颜色越深表示数据值越大,颜色越浅表示数…...