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

Dijkstra算法——邻接矩阵实现+路径记录

本文是在下面这篇文章的基础上做了一些补充,增加了路径记录的功能。具体Dijkstra的实现过程可以参考下面的这篇文章。
[jarvan:Dijkstra算法详解 通俗易懂](Dijkstra算法详解 通俗易懂 - jarvan的文章 - 知乎
https://zhuanlan.zhihu.com/p/338414118)

创建 GraphAdjMat 类
GraphAdjMat 类用来实现图的邻接矩阵,方便后续的测试,具体代码如下:

package algorithm.graph;import java.util.ArrayList;
import java.util.List;public class GraphAdjMat {private List<Integer> vertices;private List<List<Integer>> adjMat;/*** 构造函数* @param vertices 顶点列表* @param edges 边*/public GraphAdjMat(int[]vertices, int[][]edges) {this.vertices = new ArrayList<>();this.adjMat = new ArrayList<>();for(int v : vertices) {addVertex(v);}for(int[]e : edges) {addEdge(e[0],e[1],e[2]);}//设置顶点自己到自己的权重为0for(int i=0; i<vertices.length; i++) {this.adjMat.get(i).set(i, 0);}}public List<List<Integer>> getAdjMat() {return this.adjMat;}/*** 添加顶点*/public void addVertex(int val) {int n = vertices.size();vertices.add(val);List<Integer> newRow = new ArrayList<>();for(int i=0; i<n; i++) {newRow.add(-1);}adjMat.add(newRow);for(List<Integer> row : adjMat) {row.add(-1);}}/*** 移除顶点*/public void removeVertex(int index) {if(index < 0 || index >= vertices.size()) {throw new IndexOutOfBoundsException();}vertices.remove(index);adjMat.remove(index);for(List<Integer> row : adjMat) {row.remove(index);}}/*** 添加边* @param i 顶点1* @param j 顶点2* @param weight 边权重*/public void addEdge(int i, int j, int weight) {if(i<0||j<0||i>=vertices.size()||j>=vertices.size()||i==j) {throw new IndexOutOfBoundsException();}adjMat.get(i).set(j, weight);adjMat.get(j).set(i, weight);}/*** 移除边*/public void removeEdge(int i, int j) {if(i<0||j<0||i>=vertices.size()||j>=vertices.size()||i==j) {throw new IndexOutOfBoundsException();}adjMat.get(i).set(j, -1);adjMat.get(j).set(i, -1);}public void print() {System.out.println("adj mat:");for(List<Integer> row : adjMat) {for(int v : row) {System.out.printf("%3d", v);}System.out.println();}}}

GraphAdjMat 类中提供了增加顶点、移除顶点、增加边和移除边的操作。
创建 DijkstraAlg 类
该类用于实现 Dijkstra 算法,并打印指定点到所有点的最短距离和路径信息

package algorithm.graph;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** Dijkstra 算法*/
public class DijkstraAlg {public static void main(String[]args) {char[]vertexNames = {'A','B','C','D'};int[]vertices = {1,2,3,4};int[][]edges = {{0,1,1},{0,3,6},{1,2,4},{1,3,1},{2,3,1}};//构建邻接矩阵GraphAdjMat adjMat = new GraphAdjMat(vertices, edges);adjMat.print();int startVertex = 0;List<ShortestPath> result = dijkstra(adjMat.getAdjMat(),startVertex);System.out.println("dijkstra result: ");for(int i=0; i<vertexNames.length; i++) {System.out.printf("%3s -> %s distence : %d ; ",vertexNames[startVertex], vertexNames[i], result.get(i).distence);List<Integer> path = result.get(i).path;System.out.print("A -> ");for(int j=0; j<path.size(); j++) {if(j < path.size()-1) {					System.out.printf("%s -> ",vertexNames[path.get(j)]);}else {System.out.printf("%s\n", vertexNames[path.get(j)]);}}}}public static List<ShortestPath> dijkstra(List<List<Integer>> graph, int startVertex) {int len = graph.size();List<ShortestPath> result = new ArrayList<>(len);int[]notFound = new int[len];//初始化 resultfor(int i=0; i<len; i++) {ShortestPath shortestPath = new ShortestPath();shortestPath.distence = -1;shortestPath.path = new ArrayList<>();result.add(i, shortestPath);}ShortestPath startVertexPath = new ShortestPath();startVertexPath.distence = 0;startVertexPath.path = new ArrayList<>(0);result.set(startVertex,startVertexPath);//初始化 notFoundfor(int i=0; i<len; i++) {notFound[i] = graph.get(startVertex).get(i);}notFound[startVertex] = -1;//开始 Dijkstra 算法Map<Integer,List<Integer>> recordPathMap = new HashMap<>();for(int i=1; i<len; i++) {int min = Integer.MAX_VALUE;int minIndex = 0;for(int j=0; j<len; j++) {if(notFound[j] > 0 && notFound[j] < min) {min = notFound[j];minIndex = j;}}result.get(minIndex).distence = min;notFound[minIndex] = -1;//刷新 notFoundfor(int j=0; j<len; j++) {//graph.get(minIndex).get(j) > 0 用来确保 minIndex 顶点有边,result[j] == -1 用来确保 j 点没有在结果集中if(graph.get(minIndex).get(j) > 0 && result.get(j).distence == -1) {int newDistence = result.get(minIndex).distence + graph.get(minIndex).get(j);//计算合并距离如果小于直接到j点的距离,或者无法到达j点事将新距离刷新到notFound中if(newDistence < notFound[j] || notFound[j] == -1) {notFound[j] = newDistence;if(!recordPathMap.containsKey(j)) {List<Integer> tempList = new ArrayList<>(1);tempList.add(minIndex);recordPathMap.put(j, tempList);}else {							recordPathMap.get(j).add(minIndex);}}}}}System.out.println(recordPathMap);//推到路径for(int i=0; i<len; i++) {result.get(i).path.addAll(recordPathMap.getOrDefault(i, new ArrayList<>()));result.get(i).path.add(i);}return result;}public static void printArr(int[]arr, String arrName) {System.out.print(arrName);for(int i : arr) {System.out.printf("%3d", i);}System.out.println();}static class ShortestPath {public int distence;public List<Integer> path;}
}

代码在原文代码的基础上通过增加 recordPathMap 来记录最短路径,最终打印最短路径距离和对应路劲信息。
在这里插入图片描述

相关文章:

Dijkstra算法——邻接矩阵实现+路径记录

本文是在下面这篇文章的基础上做了一些补充&#xff0c;增加了路径记录的功能。具体Dijkstra的实现过程可以参考下面的这篇文章。 [jarvan&#xff1a;Dijkstra算法详解 通俗易懂](Dijkstra算法详解 通俗易懂 - jarvan的文章 - 知乎 https://zhuanlan.zhihu.com/p/338414118) …...

Vim基础操作

参考B站UP&#xff1a;正月点灯笼 vim入门教程&#xff08;共3讲&#xff09; 以下总结&#xff0c;部分搬运自评论区&#xff0c;楼主&#xff1a;-不是飞鱼QAQ&#xff0c;修改部分内容。 vim分为 命令 和 编辑 模式 i进入编辑模式&#xff08; - - INSERT - - &#xff09;…...

Mac上安装 Node.js 的版本管理工具 n,以及 n 使用,的使用

安装 最近刚更换 Mac 本进行项目的开发&#xff0c;刚上手 Mac 本还不是很熟练&#xff0c;需要安装 Node.js 的包管理工具 在 Windows 上我是实用的 nvm 来管理的 Node 版本&#xff0c;但是我尝试下载 Nvm &#xff0c;发现下载安装后的 Nvm 无法使用&#xff0c;提示 “Th…...

Node.js和npm

目录 01_Node.js01.什么是 Node.js目标讲解小结 02.fs模块-读写文件目标讲解小结 03.path模块-路径处理目标讲解小结 04.案例-压缩前端html目标讲解小结 05.认识URL中的端口号目标讲解小结 06.http模块-创建Web服务目标讲解小结 07.案例-浏览时钟目标讲解小结 02_Node.js模块化…...

leetcode每日一题43

116. 填充每个节点的下一个右侧节点指针 层序遍历嘛 /* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(N…...

每天刷两道题——第十天

1.1和为k的子数组 给你一个整数数组 n u m s nums nums 和一个整数 k k k &#xff0c;请你统计并返回 该数组中和为 k k k 的子数组的个数 。子数组是数组中元素的连续非空序列。 输入&#xff1a;nums [1,2,3], k 3 输出&#xff1a;2 前缀和 1.2如何使用 前缀和的…...

C语言入门教程,C语言学习教程(第一部分:编程基础 )一

C语言是一门面向过程的编译型语言&#xff0c;它的运行速度极快&#xff0c;仅次于汇编语言。C语言是计算机产业的核心语言&#xff0c;操作系统、硬件驱动、关键组件、数据库等都离不开C语言&#xff1b;不学习C语言&#xff0c;就不能了解计算机底层。 这套「C语言入门教程」…...

uniapp微信小程序投票系统实战 (SpringBoot2+vue3.2+element plus ) -用户信息修改实现

锋哥原创的uniapp微信小程序投票系统实战&#xff1a; uniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )_哔哩哔哩_bilibiliuniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )共计21条视频…...

C语言PDF编程书籍下载

[C.Primer.Plus&#xff08;第6版&#xff09;中文版].&#xff08;美&#xff09;普拉达.扫描版.pdf 链接: https://pan.baidu.com/s/1difCyykkBdLqgLu32PgYLw 密码: tv05 C语言程序设计教程_基于Visual.Cpp.6.0环境.pdf 链接: https://pan.baidu.com/s/1q3nRrRJyUd4H3Yp_PgA…...

VScode/Xshell连接学校服务器

vscode连学校服务器 1.连接atrust VPN2.Xshell连接服务器2.1创建一个自己的用户 3.xftp传文件4.vscode连接服务器4.1下载remote-ssh4.2连接服务器4.3激活conda环境4.4运行代码 5. pytorch版本不兼容解决方案 1.连接atrust VPN 如果是使用的是校园网&#xff0c;可以不连接 2…...

46 WAF绕过-信息收集之反爬虫延时代理池技术

目录 简要本章具体内容和安排缘由简要本课具体内容和讲课思路简要本课简要知识点和具体说明演示案例:Safedog-默认拦截机制分析绕过-未开CCSafedog-默认拦截机制分析绕过-开启CC总结&#xff1a; Aliyun_os-默认拦截机制分析绕过-简要界面BT(防火墙插件)-默认拦截机制分析绕过-…...

[Markdown] Markdown常用快捷键分类汇总

文章目录 Markdown1、标题2、列表3、强调4、链接和图片5、代码和公式6、表格和任务列表7、引用8、分割线9、脚注10、目录11、注释12、定义 Markdown Markdown是一种轻量级的标记语言&#xff0c;可以让你用简单的语法来编写格式丰富的文档。 Markdown编辑器是一种专门用于编辑…...

uniapp自定义封装只有时分秒的组件,时分秒范围选择

说实话&#xff0c;uniapp和uview的关于只有时分秒的组件实在是不行。全是日历&#xff0c;但是实际根本就不需要日历这玩意。百度了下&#xff0c;终于看到了一个只有时分秒的组件。原地址&#xff1a;原地址&#xff0c;如若侵犯请联系我删除 <template><view clas…...

SpringBoot 中 @Transactional 注解的使用

一、基本介绍 事务管理是应用系统开发中必不可少的一部分。Spring 为事务管理提供了丰富的功能支持。Spring 事务管理分为编程式和声明式的两种方式。本篇只说明声明式注解。 1、在 spring 项目中, Transactional 注解默认会回滚运行时异常及其子类&#xff0c;其它范…...

【还不了解 Dockerfile 的同学不是好测试人】

近年来 Docker 非常火&#xff0c;想要玩好 Docker 的话 Dockerfile 是绕不开的&#xff0c;这就好比想要玩好 Linux 服务器绕不开 shell 道理是一样的。 今天我们就来聊一聊 Dockerfile 怎么写&#xff0c;那些指令到底是什么意思。 前言 一、先来看一个简单的 Dockerfile #这…...

新手一键重装系统Win10步骤教程

如果我们发现电脑上的操作系统出现很严重的问题&#xff0c;不能通过简单的操作解决&#xff0c;这时候就可以选择重新安装电脑系统&#xff0c;快速解决问题。但是&#xff0c;新手用户不具备专业的装机知识&#xff0c;不知道重装Win10系统要怎么操作&#xff1f;那么可以按照…...

Ceph源码分析-在C++中,符号““和“*“有不同的用法。

在C中&#xff0c;符号"&"和"*"有不同的用法。 "&"符号&#xff1a; 在变量声明时&#xff0c;"&"用于定义引用类型。例如&#xff1a;int a 10; int& ref a; 这里的"ref"是一个引用&#xff0c;它引用了…...

Azure AI 内容安全Content Safety Studio实战

Azure AI Content Safety 检测应用程序和服务中用户生成和 AI 生成的有害内容。 Azure AI 内容安全包括文本和图像 API&#xff0c;可用于检测有害材料。 交互式 Content Safety Studio&#xff0c;可用于查看、浏览和试用用于检测不同形式的有害内容的示例代码。 关注TechLead…...

计算机网络学习笔记(四)

文章目录 1.介绍一下HTTPS的流程。2.介绍一下HTTP的失败码。3.说一说你知道的http状态码。4. 301和302有什么区别&#xff1f;5.302和304有什么区别&#xff1f;6. 请描述一次完整的HTTP请求的过程。7.什么是重定向&#xff1f;8. 重定向和请求转发有什么区别&#xff1f;9.介绍…...

typora导出html添加目录

typora导出html添加目录 使用方法 首先要从typora导出html文件&#xff0c;之后用记事本编辑器html文件 找到文档最后面&#xff0c;如图&#xff1a; 用文字编辑类工具打开sideBar.txt&#xff0c;复制其中所有内容【内容在下面】 在如上图的位置插入所复制的内容 打开修改…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...