当前位置: 首页 > news >正文

【数据结构与算法 | 图篇】Dijkstra算法(单源最短路径算法)

1. 前言

由图:

d3ed8f6785a9492ea387ff28f164549c.png

如果我们想要求得节点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;}}}}
}

如图:

4db3900871144f95879d51e5d876d080.png

输出为:

v1   0
v2   7
v3   9
v4   20
v5   20
v6   11

5. 改进的Dijkstra算法

上述的ChooseMinDistVertex方法可以改进,即使用优先队列。思路一致,这里就不多写了。

相关文章:

【数据结构与算法 | 图篇】Dijkstra算法(单源最短路径算法)

1. 前言 由图&#xff1a; 如果我们想要求得节点1到节点5&#xff08;也可以是其他节点&#xff09;的最短路径&#xff0c;我们可以使用Dijkstra算法。 2. 步骤与思路 1. 将所有顶点标记为未访问(顶点类的visited属性设置为false)。创建一个未访问顶点的集合。 2. 为每个顶…...

windows c转linux c要做的事情。

写在开头&#xff1a; 最近的copy项目要转到windows版本了&#xff0c;一直在跟进做这个事情。 直入主题说下移植过程中可能涉及以下几个方面的调整&#xff1a;‌ 编译器和工具链的更改&#xff1a;‌Windows和Linux使用不同的编译器和工具链&#xff0c;‌因此需要在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 an​xnan−1​xn−1...a1​xa0​0 等式左边是一元多项式。 所有一元多项式组成的集合称为一元多项式环。...

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 支持包&#xff1a; (其实就一个文件&#xff0c;搞过来就能用) sudo apt-get install python-redis #方法2、 sudo pip install redis...

YJ0043定制版抖音电商卷抢购系统带回收商城抖音电商优惠卷投资理财系统

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

如何选择图片和视频

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

html+css网页制作 电商华为商城首页 ui还原度100%

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

EDAS(企业级应用服务)

1 :介绍 1&#xff1a;edas 提供了应用&#xff0c;开发&#xff0c;部署&#xff0c;监控&#xff0c;运维。同时支持 spring cloud, dubbo ,HSF 2:Ali-Tomcat 基于tomcat改造的Servlet容器。支持原有功能&#xff0c;它在启动时会自动加载Pandora&#xff08;潘多拉&#x…...

简单工厂,工厂方法 和 抽象工厂

这三种模式&#xff0c; 都是创建类型的模式&#xff0c; 将对象的创建流程封装起来供客户调用 简单工厂模式 简介: 和策略模式一样&#xff0c;就是针对不通的参数&#xff0c; 返回不通的实例而已 问题: 没有遵循开闭原则&#xff0c; 如果我们想增加一种类&#xff0c; 那…...

python 压力测试脚本

需求&#xff1a; 生成一个12位不重复的随机数将随机数赋值给Json 串中的 orderCode字段将Json用ECB 指定 key为bJXQezYtR4ZSNK4p进行加密并作为值传给{ “data”: “” }设置每秒30个并发持续1分钟调用接口接口输出测试测试报告 代码示例 import json import random import…...

【Linux】多线程7——线程池

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

Linux Shell实例

1.查空行 答案&#xff1a; awk /^$/{print NR} file1.txt#awk:一个强大的文本分析工具&#xff0c;把文件逐行的读入&#xff0c;以空格为默认分隔符将每行切片&#xff0c;切开的部分再进行分析#处理。 #1&#xff09;基本语法 #awk [选项参数]/pattern1/{action1} /pattern…...

Linux~MySQL数据库具体操作

一、数据库的字符集编码设置 &#xff08;一&#xff09;查看数据库默认的字符集 MariaDB [(none)]> show variables like %character%; ------------------------------------------------------ | Variable_name | Value | ------------…...

Unity WebGL平台Hybrid Generate All报错undefined symbol sendfile

详细报错信息如下&#xff1a; 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.多线程 什么是线程&#xff1a; 线程右进程创建的&#xff0c;是进程的一个实体 一个进程可以有多个线程 并发&#xff1a;同一个时刻&#xff0c;多个任务交替执行&#xff0c;造成一种貌似同时的错觉 并行&#xff1a;同一个时刻&#xff0c;多个任务同时执行&#x…...

0003 保险的会计要素及其计量属性

与一般行业相同&#xff0c;保险业的会计要素主要包括资产、负债、所有者权益、收入、成本与费用以及利润六个方面。然而&#xff0c;在某些特定的要素上&#xff0c;保险业展示了其独特之处。 资产&#xff1a;由于保险本质上是一种承诺而非实物商品&#xff0c;因此保险业不持…...

Swift版本控制的艺术:掌握代码演化的魔杖

标题&#xff1a;Swift版本控制的艺术&#xff1a;掌握代码演化的魔杖 在Swift开发的世界中&#xff0c;代码的版本管理是一个核心议题。它不仅关系到代码的组织和追踪&#xff0c;更是团队协作和项目持续交付的关键。本文将深入探讨如何在Swift中利用版本管理工具&#xff0c…...

学习实战:生活垃圾自动识别与分类系统的实现

引言 在日常生活中&#xff0c;垃圾分类是保护环境的重要措施之一。然而&#xff0c;手动分类不仅耗时&#xff0c;还容易出错。基于深度学习的垃圾检测与分类系统能够自动识别和分类不同类型的垃圾&#xff0c;从而提高分类效率。 目录 项目概述 项目背景与意义系统功能介绍…...

Swift模块化构建:解锁代码重用的金钥匙

标题&#xff1a;Swift模块化构建&#xff1a;解锁代码重用的金钥匙 在Swift编程的宏伟蓝图中&#xff0c;模块化不仅是提升代码组织性的关键&#xff0c;更是实现高效开发与维护的法宝。本文将深入探讨Swift模块化构建工具的使用&#xff0c;揭示如何通过模块化将代码转化为可…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...