当前位置: 首页 > 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;复制其中所有内容【内容在下面】 在如上图的位置插入所复制的内容 打开修改…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

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

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

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...