【数据结构与算法 | 图篇】Dijkstra算法(单源最短路径算法)
1. 前言
由图:
如果我们想要求得节点1到节点5(也可以是其他节点)的最短路径,我们可以使用Dijkstra算法。
2. 步骤与思路
1. 将所有顶点标记为未访问(顶点类的visited属性设置为false)。创建一个未访问顶点的集合。
2. 为每个顶点分配一个临时距离值:
- 对于我们的初始顶点,将其设置为0;
- 对于所有其他顶点,将其设置为无穷大。
3. 每次选择最小临时距离的未访问节点作为当前顶点。
4. 对于当前顶点,遍历其所有未访问的邻居,并更新它们的临时距离为更小。
- 例如,1->6的距离是14,而1->3->6的距离是11。这时将距离更新为11.
- 否则,将保留上次距离值。
5. 当前顶点的邻居处理完后,把它从未访问集合中删除。
3. 顶点类与边类
public class Vertex {// 顶点的名字,用来区分顶点String name;// 与该顶点有关的边的集合List<Edge> edges;// 判断是否已经被遍历boolean visited = false;// 初始距离为无穷大int dist = INF;// INF表示无穷大final static int INF = Integer.MAX_VALUE;// 该顶点在最短路径中的前一个顶点Vertex prev = null;public Vertex(String name) {this.name = name;}public String getName() {return name;}
}public class Edge {// 表示边上被箭头指向的顶点Vertex linked;// 权重int weight;public Edge(Vertex linked) {this.linked = linked;weight = 1;}public Edge(Vertex linked, int weight) {this.linked = linked;this.weight = weight;}
}
4. 总代码:
public class Dijkstra {public static void main(String[] args) {List<Vertex> list = new ArrayList<>();// 建立顶点联系Vertex v1 = new Vertex("1");Vertex v2 = new Vertex("2");Vertex v3 = new Vertex("3");Vertex v4 = new Vertex("4");Vertex v5 = new Vertex("5");Vertex v6 = new Vertex("6");v1.edges = new ArrayList<>();v1.edges.add(new Edge(v3, 9));v1.edges.add(new Edge(v2, 7));v1.edges.add(new Edge(v6, 14));v2.edges = new ArrayList<>();v2.edges.add(new Edge(v4, 15));v3.edges = new ArrayList<>();v3.edges.add(new Edge(v6, 2));v3.edges.add(new Edge(v4, 11));v4.edges = new ArrayList<>();v4.edges.add(new Edge(v5, 6));v5.edges = new ArrayList<>();v6.edges = new ArrayList<>();v6.edges.add(new Edge(v5, 9));// 第1步:list.add(v1);list.add(v2);list.add(v3);list.add(v4);list.add(v5);list.add(v6);// v1作为初始顶点dijkstra(list, v1);}public static void dijkstra(List<Vertex> list, Vertex v) {List<Vertex> graph = new ArrayList<>(list);// 将初始顶点v的dist值设置为0v.dist = 0;while (!graph.isEmpty()){// 第3步:每次选择最小的临时距离的未访问节点作为当前节点Vertex i = ChooseMinDistVertex(graph);UpdateNeighboursDist(i);graph.remove(i);// 表示已经被处理完了i.visited = true;}
// for (Vertex i : list){
// System.out.println("v" + i.name + " " + i.dist);
// }// 打印最短路径中,一个顶点的前一个顶点是谁for(Vertex i : list){System.out.println("v" + i.name + (i.prev != null ? i.prev : null));}}private static Vertex ChooseMinDistVertex(List<Vertex> list){int min = 0;int dist = list.get(min).dist;for(int i = 0; i < list.size(); i++) {if(dist > list.get(i).dist){min = i;dist = list.get(i).dist;}}return list.get(min);}private static void UpdateNeighboursDist(Vertex v) {// 对于当前顶点,遍历其所有未访问的顶点for(Edge e : v.edges){if(!e.linked.visited){if(v.dist + e.weight < e.linked.dist){e.linked.dist = v.dist + e.weight;e.linked.prev = v;}}}}
}
如图:
输出为:
v1 0
v2 7
v3 9
v4 20
v5 20
v6 11
5. 改进的Dijkstra算法
上述的ChooseMinDistVertex方法可以改进,即使用优先队列。思路一致,这里就不多写了。
相关文章:

【数据结构与算法 | 图篇】Dijkstra算法(单源最短路径算法)
1. 前言 由图: 如果我们想要求得节点1到节点5(也可以是其他节点)的最短路径,我们可以使用Dijkstra算法。 2. 步骤与思路 1. 将所有顶点标记为未访问(顶点类的visited属性设置为false)。创建一个未访问顶点的集合。 2. 为每个顶…...
windows c转linux c要做的事情。
写在开头: 最近的copy项目要转到windows版本了,一直在跟进做这个事情。 直入主题说下移植过程中可能涉及以下几个方面的调整: 编译器和工具链的更改:Windows和Linux使用不同的编译器和工具链,因此需要在Windo…...

【高等代数笔记】002.高等代数研究对象(二)
1. 高等代数的研究对象 1.4 一元高次方程的求根 a n x n a n − 1 x n − 1 . . . a 1 x a 0 0 a_{n}x^{n}a_{n-1}x^{n-1}...a_{1}xa_{0}0 anxnan−1xn−1...a1xa00 等式左边是一元多项式。 所有一元多项式组成的集合称为一元多项式环。...

ubuntu服务器部署的mysql本地连不上的问题
试过了网上的所有方法,都连不上,可以执行: SELECT user, host, plugin FROM mysql.user WHERE user root; 查一下:plungin这个连接插件是不是auth_socket, auth_socket是只能本地连接的插件,需要修改: ALTER USER root% IDENTIFIED WITH mysql_native_password BY your_pass…...
python redis安装
python redis安装 #方法1、 sudo apt-get install redis-server python 支持包: (其实就一个文件,搞过来就能用) sudo apt-get install python-redis #方法2、 sudo pip install redis...

YJ0043定制版抖音电商卷抢购系统带回收商城抖音电商优惠卷投资理财系统
系统是基于逍遥商城二开的系统,pc手机端都新增了邀请码验证 手机端重新定制的UI,前端产品不至于抖音卷也可以自行更改其他产品 用户前端下单,后台订单可以直接回收,后台支持设置默认邀请码和抢卷时间限制...

如何选择图片和视频
文章目录 1. 概念介绍2. 方法与细节2.1 实现方法2.2 具体细节 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何选择视频文件"相关的内容,本章回中将介绍如何混合选择图片和视频文件.闲话休提,让我们一起Talk Flutter吧。 1. 概念介绍 我…...

html+css网页制作 电商华为商城首页 ui还原度100%
htmlcss网页制作 电商华为商城首页 ui还原度100% 网页作品代码简单,可使用任意HTML编辑软件(如:Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作)。 获取源码…...

EDAS(企业级应用服务)
1 :介绍 1:edas 提供了应用,开发,部署,监控,运维。同时支持 spring cloud, dubbo ,HSF 2:Ali-Tomcat 基于tomcat改造的Servlet容器。支持原有功能,它在启动时会自动加载Pandora(潘多拉&#x…...
简单工厂,工厂方法 和 抽象工厂
这三种模式, 都是创建类型的模式, 将对象的创建流程封装起来供客户调用 简单工厂模式 简介: 和策略模式一样,就是针对不通的参数, 返回不通的实例而已 问题: 没有遵循开闭原则, 如果我们想增加一种类, 那…...
python 压力测试脚本
需求: 生成一个12位不重复的随机数将随机数赋值给Json 串中的 orderCode字段将Json用ECB 指定 key为bJXQezYtR4ZSNK4p进行加密并作为值传给{ “data”: “” }设置每秒30个并发持续1分钟调用接口接口输出测试测试报告 代码示例 import json import random import…...

【Linux】多线程7——线程池
1.线程池的概念 1.1.池化技术 池化技术指的是提前准备一些资源,在需要时可以重复使用这些预先准备的资源。 在系统开发过程中,我们经常会用到池化技术。通俗的讲,池化技术就是:把一些资源预先分配好,组织到对象池中…...

Linux Shell实例
1.查空行 答案: awk /^$/{print NR} file1.txt#awk:一个强大的文本分析工具,把文件逐行的读入,以空格为默认分隔符将每行切片,切开的部分再进行分析#处理。 #1)基本语法 #awk [选项参数]/pattern1/{action1} /pattern…...
Linux~MySQL数据库具体操作
一、数据库的字符集编码设置 (一)查看数据库默认的字符集 MariaDB [(none)]> show variables like %character%; ------------------------------------------------------ | Variable_name | Value | ------------…...

Unity WebGL平台Hybrid Generate All报错undefined symbol sendfile
详细报错信息如下: Library\Bee\artifacts\WebGL\build\debug_WebGL_wasm\build.js: undefined symbol: sendfile (referenced by top-level compiled C/C code) UnityEditor.BuildPipeline:BuildPlayer (UnityEditor.BuildPlayerOptions) HybridCLR.Editor.Comman…...
Java高级Day28-多线程
83.多线程 什么是线程: 线程右进程创建的,是进程的一个实体 一个进程可以有多个线程 并发:同一个时刻,多个任务交替执行,造成一种貌似同时的错觉 并行:同一个时刻,多个任务同时执行&#x…...
0003 保险的会计要素及其计量属性
与一般行业相同,保险业的会计要素主要包括资产、负债、所有者权益、收入、成本与费用以及利润六个方面。然而,在某些特定的要素上,保险业展示了其独特之处。 资产:由于保险本质上是一种承诺而非实物商品,因此保险业不持…...
Swift版本控制的艺术:掌握代码演化的魔杖
标题:Swift版本控制的艺术:掌握代码演化的魔杖 在Swift开发的世界中,代码的版本管理是一个核心议题。它不仅关系到代码的组织和追踪,更是团队协作和项目持续交付的关键。本文将深入探讨如何在Swift中利用版本管理工具,…...
学习实战:生活垃圾自动识别与分类系统的实现
引言 在日常生活中,垃圾分类是保护环境的重要措施之一。然而,手动分类不仅耗时,还容易出错。基于深度学习的垃圾检测与分类系统能够自动识别和分类不同类型的垃圾,从而提高分类效率。 目录 项目概述 项目背景与意义系统功能介绍…...
Swift模块化构建:解锁代码重用的金钥匙
标题:Swift模块化构建:解锁代码重用的金钥匙 在Swift编程的宏伟蓝图中,模块化不仅是提升代码组织性的关键,更是实现高效开发与维护的法宝。本文将深入探讨Swift模块化构建工具的使用,揭示如何通过模块化将代码转化为可…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...