Java手写最短路径算法和案例拓展
Java手写最短路径算法和案例拓展
1. 算法手写的必要性
在实际开发中,经常需要处理图的最短路径问题。虽然Java提供了一些图算法库,但手写最短路径算法的必要性体现在以下几个方面:
- 理解算法原理:手写算法可以帮助我们深入理解最短路径算法的原理和思路,提高对算法的理解程度。
- 灵活性和可定制性:手写算法可以根据具体需求进行定制,满足不同场景下的需求。
- 性能优化:手写算法可以根据具体情况进行性能优化,提高算法的效率。
2. 市场调查
在市场调查中,我们发现最短路径算法在物流、导航、网络通信等领域有着广泛的应用。例如,物流公司需要确定最短路径来优化运输成本;导航软件需要找到最短路径来指导用户行驶;网络通信需要确定最短路径来提高数据传输效率。
3. 实现思路原理
为了更好地理解最短路径算法的实现思路,我们使用Mermanid代码表示思维导图,解释实现思路的原理。
上述思维导图描述了最短路径算法的基本思路:从起点开始,逐步选择下一个顶点,并更新距离和路径,直到到达目标顶点,输出最短路径。
4. 实现的详细介绍和详细步骤
步骤1:初始化距离和路径
在开始算法之前,需要初始化距离和路径。距离表示从起点到每个顶点的最短距离,路径表示从起点到每个顶点的最短路径。
// 初始化距离和路径
for (int i = 0; i < vertexCount; i++) {distance[i] = Integer.MAX_VALUE;path[i] = -1;
}
distance[start] = 0;
步骤2:选择起点
选择起点作为当前顶点,并标记为已访问。
int current = start;
visited[current] = true;
步骤3:更新距离和路径
遍历当前顶点的所有邻接顶点,更新距离和路径。
for (int neighbor : getNeighbors(current)) {if (!visited[neighbor]) {int newDistance = distance[current] + getWeight(current, neighbor);if (newDistance < distance[neighbor]) {distance[neighbor] = newDistance;path[neighbor] = current;}}
}
步骤4:选择下一个顶点
从未访问的顶点中选择距离最小的顶点作为下一个顶点。
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < vertexCount; i++) {if (!visited[i] && distance[i] < minDistance) {minDistance = distance[i];current = i;}
}
visited[current] = true;
步骤5:重复选择下一个顶点
重复步骤3和步骤4,直到所有顶点都被访问。
步骤6:输出最短路径
根据路径数组,输出从起点到目标顶点的最短路径。
List<Integer> shortestPath = new ArrayList<>();
int vertex = target;
while (vertex != -1) {shortestPath.add(vertex);vertex = path[vertex];
}
Collections.reverse(shortestPath);
5. 手写实现总结及必要性
通过手写最短路径算法的实现,我们深入理解了算法的原理和思路。手写实现能够提高我们对算法的理解程度,并且具有灵活性和可定制性,可以根据具体需求进行定制和性能优化。手写最短路径算法在物流、导航、网络通信等领域有着广泛的应用前景。
5.1 手写完整代码
以下是一个使用Dijkstra算法求解最短路径的完整代码示例:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class DijkstraAlgorithm {private int vertexCount;private int[][] adjacencyMatrix;public DijkstraAlgorithm(int vertexCount) {this.vertexCount = vertexCount;adjacencyMatrix = new int[vertexCount][vertexCount];}public void addEdge(int source, int destination, int weight) {adjacencyMatrix[source][destination] = weight;adjacencyMatrix[destination][source] = weight;}public List<Integer> shortestPath(int start, int target) {int[] distance = new int[vertexCount];int[] path = new int[vertexCount];boolean[] visited = new boolean[vertexCount];// 初始化距离和路径Arrays.fill(distance, Integer.MAX_VALUE);Arrays.fill(path, -1);distance[start] = 0;// 选择起点int current = start;visited[current] = true;// 更新距离和路径for (int neighbor = 0; neighbor < vertexCount; neighbor++) {if (!visited[neighbor] && adjacencyMatrix[current][neighbor] > 0) {int newDistance = distance[current] + adjacencyMatrix[current][neighbor];if (newDistance < distance[neighbor]) {distance[neighbor] = newDistance;path[neighbor] = current;}}}// 选择下一个顶点for (int i = 1; i < vertexCount; i++) {int minDistance = Integer.MAX_VALUE;for (int j = 0; j < vertexCount; j++) {if (!visited[j] && distance[j] < minDistance) {minDistance = distance[j];current = j;}}visited[current] = true;// 更新距离和路径for (int neighbor = 0; neighbor < vertexCount; neighbor++) {if (!visited[neighbor] && adjacencyMatrix[current][neighbor] > 0) {int newDistance = distance[current] + adjacencyMatrix[current][neighbor];if (newDistance < distance[neighbor]) {distance[neighbor] = newDistance;path[neighbor] = current;}}}}// 输出最短路径List<Integer> shortestPath = new ArrayList<>();int vertex = target;while (vertex != -1) {shortestPath.add(vertex);vertex = path[vertex];}Collections.reverse(shortestPath);return shortestPath;}public static void main(String[] args) {DijkstraAlgorithm graph = new DijkstraAlgorithm(6);graph.addEdge(0, 1, 2);graph.addEdge(0, 2, 4);graph.addEdge(1, 2, 1);graph.addEdge(1, 3, 7);graph.addEdge(2, 4, 3);graph.addEdge(3, 4, 1);graph.addEdge(3, 5, 5);graph.addEdge(4, 5, 2);List<Integer> shortestPath = graph.shortestPath(0, 5);System.out.println("Shortest Path: " + shortestPath);}
}
以上代码实现了一个Dijkstra算法的最短路径求解器。在示例中,我们创建了一个有6个顶点的图,并添加了8条边。然后,我们使用Dijkstra算法计算从顶点0到顶点5的最短路径,并打印出结果。输出结果为Shortest Path: [0, 2, 4, 5]
,表示从顶点0到顶点5的最短路径为0 -> 2 -> 4 -> 5。
6. 拓展案例
下面是一个拓展案例,展示了每个步骤的代码进行文字描述:
// 步骤1:初始化距离和路径
for (int i = 0; i < vertexCount; i++) {distance[i] = Integer.MAX_VALUE;path[i] = -1;
}
distance[start] = 0;// 步骤2:选择起点
int current = start;
visited[current] = true;// 步骤3:更新距离和路径
for (int neighbor : getNeighbors(current)) {if (!visited[neighbor]) {int newDistance = distance[current] + getWeight(current, neighbor);if (newDistance < distance[neighbor]) {distance[neighbor] = newDistance;path[neighbor] = current;}}
}// 步骤4:选择下一个顶点
int minDistance = Integer.MAX_VALUE;
for (int i = 0; i < vertexCount; i++) {if (!visited[i] && distance[i] < minDistance) {minDistance = distance[i];current = i;}
}
visited[current] = true;// 步骤5:重复选择下一个顶点// 步骤6:输出最短路径
List<Integer> shortestPath = new ArrayList<>();
int vertex = target;
while (vertex != -1) {shortestPath.add(vertex);vertex = path[vertex];
}
Collections.reverse(shortestPath);
通过以上拓展案例,我们可以更加清晰地了解每个步骤的代码实现和作用。
相关文章:
Java手写最短路径算法和案例拓展
Java手写最短路径算法和案例拓展 1. 算法手写的必要性 在实际开发中,经常需要处理图的最短路径问题。虽然Java提供了一些图算法库,但手写最短路径算法的必要性体现在以下几个方面: 理解算法原理:手写算法可以帮助我们深入理解最…...

深度学习实战51-基于Stable Diffusion模型的图像生成原理详解与项目实战
大家好,我是微学AI,今天给大家介绍一下深度学习实战51-基于Stable Diffusion模型的图像生成原理详解与项目实战。大家知道现在各个平台发的漂亮小姐姐,漂亮的图片是怎么生成的吗?这些生成的底层原理就是用到了Stable Diffusion模型。Stable Diffusion是一种基于深度学习的图…...

基于matlab实现的多普勒脉冲雷达回波仿真
完整程序: clear all;clc;close all; fc3e9; %载波频率 PRF2000; Br5e6; %带宽 fs10*Br; %采样频率 Tp5e-6; %脉宽 KrBr/Tp; %频率变化率 c3e8; %光速 lamda…...
Linux服务器中安装Anaconda+Tensorflow+Keras
Anaconda安装 从https://repo.anaconda.com/archive/查看你需要下载的Anaconda版本,例如2020.11的x86_64(uname -a 查看linux框架)版下载Anaconda到linux服务器, wget https://repo.anaconda.com/archive/Anaconda3-2020.11-Li…...

ubuntu+.net6+docker 应用部署教程
先期工作 1、本地首先安装 Docker Desktop 2、本地装linux in windows 3、生成镜像 后期工作 1、云服务器部署 生成镜像方法 1、生成Dockerfile配置文件 开发工具visual studio 2022 如果项目已经存在,可以选中项目,右键点击->选择添加Docker…...

Spring常见面试题总结
什么是Spring Spring是一个轻量级Java开发框架,目的是为了解决企业级应用开发的业务逻辑层和其他各层的耦合问题,以提高开发效率。它是一个分层的JavaSE/JavaEE full-stack(一站式)轻量级开源框架,为开发Java应用程序…...

Git全套命令使用
日升时奋斗,日落时自省 目录 1、Git安装 1.1、创建git本地仓库 1.2、配置Git 1.3、认识Git内部区分 2、Git应用操作 2.1、添加文件 2.2、查看日志 2.3、查看修改信息 2.4、查看添加信息 3、版本回退 4、撤销修改 4.1、工作区撤销 4.2、已经add…...

【陕西理工大学-数学软件实训】数学实验报告(8)(数值微积分与方程数值求解)
目录 一、实验目的 二、实验要求 三、实验内容与结果 四、实验心得 一、实验目的 1. 掌握求数值导数和数值积分的方法。 2. 掌握代数方程数值求解的方法。 3. 掌握常微分方程数值求解的方法。 二、实验要求 1. 根据实验内容,编写相应的MATLAB程序,…...

Vue3为什么推荐使用ref而不是reactive
为什么推荐使用ref而不是reactive reactive本身具有很大局限性导致使用过程需要额外注意,如果忽视这些问题将对开发造成不小的麻烦;ref更像是vue2时代option api的data的替代,可以存放任何数据类型,而reactive声明的数据类型只能是对象; 先抛出结论,再详细说原因:非必要不用rea…...
JavaScript函数this指向
一、this的指向规则 1.this到底指向什么呢? 我们先来看一个让人困惑的问题: 定义一个函数,我们采用三种不同的方式对它进行调用,它产生了三种不同的结果 // 定义函数 function foo(name) {console.log("foo函数:", …...

Java的序列化
写在前面 本文看下序列化和反序列化相关的内容。 源码 。 1:为什么,什么是序列化和反序列化 Java对象是在jvm的堆中的,而堆其实就是一块内存,如果jvm重启数据将会丢失,当我们希望jvm重启也不要丢失某些对象ÿ…...
计算机二级python简单应用题刷题笔记(一)
计算机二级python简单应用题刷题笔记(一) 1、词频统计:键盘输入一组我国高校所对应的学校类型,以空格分隔,共一行。2、找最大值、最小值、平均分:键盘输入小明学习的课程名称及考分等信息,信息间…...

Spring注解家族介绍: @RequestMapping
前言: 今天我们来介绍RequestMapping这个注解,这个注解的内容相对来讲比较少,篇幅会比较短。 目录 前言: RequestMapping 应用场景: 总结: RequestMapping RequestMapping 是一个用于映射 HTTP 请求…...

系统架构设计师(第二版)学习笔记----信息安全系统及信息安全技术
【原文链接】系统架构设计师(第二版)学习笔记----信息加解密技术 文章目录 一、信息安全系统的组成框架1.1 信息安全系统组成框架1.2 信息安全系统技术内容1.3 常用的基础安全设备1.4 网络安全技术内容1.5 操作系统安全内容1.6 操作系统安全机制1.7 数据…...

交换机的工作原理(含实例,华为ensp操作)
目录 1.交换机学习和转发 案例 1.设置静态地址表项 2.配置黑洞mac地址表项 1.交换机学习和转发 交换机工作在数据链路层。当交换机从某个端口收到一个帧时,它并不是向所有的接口转发此帧,而是根据此帧的目的MAC地址&a…...

从字符串中删除指定字符
任务描述 编写一个函数实现功能:从字符串中删除指定的字符。同一字母的大、小写按不同字符处理。例如:程序执行时输入字符串:turbo c and Borland c,从键盘输入字符n,则输出后变为:turbo c ad Borlad c。如…...
Xcode14.3.1 真机调试iOS17的方法(无iOS17 DeviceSupport)
由于iOS17需要使用Xcode15 才能调试,而当前Xcode15都是beta,正式版还未出,那么要真机调试iOS17的方式一般有两种: 方法一: 一种是下载新的Xcode15 beta版 (但Xcode包一般比较大,好几个G&#…...
JWT基础
概念 JSON Web Token本质上就是一串字符串,一串包含了很多信息的字符串令牌拥有三个部分头部-包含加密算法和令牌类型{"alg":"算法名称","type":"JWT"}负载-包含数据和信息-七个官方默认-也可以自己定义内容{issÿ…...
关于远程工作的面试可能存在的陷阱
附上看到的完整帖子地址:面试 POPER 的后端开发工程师的离奇经历 分享一下我遇到过的,我至少面试过10个远程工作,其中有3个的面试是直接让我完成一个需求的,前两次都耐心做了,第3次看到相同要求时我都懒得回复了&…...

Qt5开发及实例V2.0-第一章Qt概述
Qt5开发及实例V2.0-第一章-Qt概述 第一章-Qt概述1.1 什么是Qt1.2 Qt 5的安装1.2.1 下载安装Qt 51.2.2 运行Qt 5 Creator1.2.3 Qt 5开发环境 1.3 Qt 5开发步骤及实例1.3.1 设计器Qt 5 Designer实现1.3.2 代码实现简单实例 L1.2 Qt 5安装:概念解析L1.3 Qt 5开发步骤及…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...

基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...

GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...

Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...