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

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...