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

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...