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

迪瑞克斯拉算法

迪锐克斯拉算法
简单来说就是在有向图中,给定一个图中具体的出发点,从这个点出发能够到达的所有的点,每个点的最短距离是多少。到不了的点,距离则是正无穷。有向,无负权重,可以有环
所以说,迪锐克斯拉算法是生成一个从源点出发到各个点的最小距离表。
举例:有向图如图所示
在这里插入图片描述

从给定的出发点a出发,最终要获得的是a到b,c,d,e每个点之间的最短距离。默认a到自己的距离是0,其他的点还没到达的点的距离是正无穷。已经确定的答案不动,在没有确定的记录中找一个最小的出来

abcde
0正无穷正无穷正无穷正无穷

所以先从a点出发的三条边1,2,6。中找出权重为1的边,ad距离为1,小于之前的正无穷(比之前距离小),所以更新a到d之间的距离,bcd同理。所以更新完后距离如下:

abcde
0261正无穷

此时,从a出发的三条边已经走完,所以a点确定下来,再也不动。
其余没有确定的记录中d是最短的(从a出发到b的距离为1),所以从d开始向下找(d属于中间的跳点)。
d出发的边有两条,分别是dc和de。其中dc距离为2,再加上之前a到d的距离为1,所以此时a到c的距离经过d跳转后为3,小于之前的6,所以更新ac之间距离,同样de距离7小于正无穷。所以也进行更新。d也确定了。

abcde
02317

接下来从不确定的记录中根据最小的向下找。b点出发的边有一条be,be距离9加上a到b的距离2,所以be距离为11,大于之前的,不更新。b也确定了。

abcde
02317

还剩下c,从c点出发的边有两条,cb和ce,因为b点已经确定了不再动,所以一看ce一条,ce距离为3,a到c距离为3,所以ae之间距离为6,小于之前,更新e点距离。

abcde
02316

代码
根据上面的分析进行代码的实现,不过getMinDistanceAndUnSelectNode有瑕疵,因为每找一个minNode就会在集合中都遍历一次。会在下面进行代码优化。

  public static HashMap<Node, Integer> dijkstra1(Node from) {HashMap<Node, Integer> distanceMap = new HashMap<>();distanceMap.put(from, 0);//已经确定的边;HashSet<Node> selectedNodes = new HashSet<>();//根据已经确定的记录 和 map,找出没确定的中最小的记录Node minNode = getMinDistanceAndUnSelectNode(distanceMap, selectedNodes);while (minNode != null) {int distance = distanceMap.get(minNode);for (Edge edge : minNode.edges) {Node toNode = edge.to;if (!distanceMap.containsKey(toNode)) {distanceMap.put(toNode, distance + edge.weight);} else {//edge.weight + distance 当前边的权重 + 我此时当做跳点的距离。//distanceMap.get(toNode) 已经存在的距离distanceMap.put(toNode, Math.min(distanceMap.get(toNode), (edge.weight + distance)));}}//所有的边都已经遍历完,这个点可以确定了,放到确定的集合中。selectedNodes.add(minNode);//再次获取最小的记录minNode = getMinDistanceAndUnSelectNode(distanceMap, selectedNodes);}return distanceMap;}public static Node getMinDistanceAndUnSelectNode(HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNode) {Node minNode = null;int minDistance = Integer.MAX_VALUE;for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {Node node = entry.getKey();int distance = entry.getValue();if (!selectedNode.contains(node) && distance < minDistance) {minDistance = distance;minNode = node;}}return minNode;}

相关文章:

迪瑞克斯拉算法

迪锐克斯拉算法 简单来说就是在有向图中&#xff0c;给定一个图中具体的出发点&#xff0c;从这个点出发能够到达的所有的点&#xff0c;每个点的最短距离是多少。到不了的点&#xff0c;距离则是正无穷。有向&#xff0c;无负权重&#xff0c;可以有环。 所以说&#xff0c;迪…...

数据结构:力扣OJ题(每日一练)

目录 题一&#xff1a;环形链表 思路一&#xff1a; 题二&#xff1a;复制带随机指针的链表 思路一&#xff1a; 本人实力有限可能对一些地方解释的不够清晰&#xff0c;可以自己尝试读代码&#xff0c;望海涵&#xff01; 题一&#xff1a;环形链表 给定一个链表的头节点…...

【论文阅读】基于深度学习的时序预测——Informer

系列文章链接 论文一&#xff1a;2020 Informer&#xff1a;长时序数据预测 论文二&#xff1a;2021 Autoformer&#xff1a;长序列数据预测 论文三&#xff1a;2022 FEDformer&#xff1a;长序列数据预测 论文四&#xff1a;2022 Non-Stationary Transformers&#xff1a;非平…...

机器学习 | Python实现GBDT梯度提升树模型设计

机器学习 | Python实现GBDT梯度提升树模型设计 目录 机器学习 | Python实现GBDT梯度提升树模型设计基本介绍模型描述模型使用参考资料基本介绍 机器学习 | Python实现GBDT梯度提升树模型设计。梯度提升树(Grandient Boosting)是提升树(Boosting Tree)的一种改进算法,GBDT也…...

elementUi表单恢复至初始状态并不触发表单验证

elementUi表单恢复至初始状态并不触发表单验证 1.场景再现2.解决方法 1.场景再现 左侧是树形列表&#xff0c;右侧是显示节点的详情&#xff0c;点击按钮应该就是新增一个规则的意思&#xff0c;表单内容是没有改变的&#xff0c;所以就把需要把表单恢复至初始状态并不触发表单…...

大模型相关知识

一. embedding 简单来说&#xff0c;embedding就是用一个低维的向量表示一个物体&#xff0c;可以是一个词&#xff0c;或是一个商品&#xff0c;或是一个电影等等。这个embedding向量的性质是能使距离相近的向量对应的物体有相近的含义&#xff0c;比如 Embedding(复仇者联盟)…...

无法在 macOS Ventura 上启动 Multipass

异常信息 ➜ ~ sudo multipass authenticate Please enter passphrase: authenticate failed: Passphrase is not set. Please multipass set local.passphrase with a trusted client. ➜ ~ multipass set local.passphrase Please enter passphrase: Please re-enter…...

算法通关村第六关——原来如此简单

层次遍历&#xff1a;又叫广度优先遍历。就是从根节点开始&#xff0c;先访问根节点下面一层全部元素&#xff0c;再访问之后的层次&#xff0c;直到访问完二叉树的最后一层。 我们先看一下基础的层次遍历题&#xff0c;力扣102题&#xff1a;给你一个二叉树&#xff0c;请你返…...

企业权限管理(八)-登陆使用数据库认证

Spring Security 使用数据库认证 在 Spring Security 中如果想要使用数据进行认证操作&#xff0c;有很多种操作方式&#xff0c;这里我们介绍使用 UserDetails 、 UserDetailsService来完成操作。 UserDetails public interface UserDetails extends Serializable { Collecti…...

第一百二十五天学习记录:C++提高:STL-deque容器(下)(黑马教学视频)

deque插入和删除 功能描述&#xff1a; 向deque容器中插入和删除数据 函数原型&#xff1a; 两端插入操作&#xff1a; push_back(elem); //在容器尾部添加一个数据 push_front(elem); //在容器头部插入一个数据 pop_back(); //删除容器最后一个数据 pop_front(); //删除容器…...

案例12 Spring MVC入门案例

网页输入http://localhost:8080/hello&#xff0c;浏览器展示“Hello Spring MVC”。 1. 创建项目 选择Maven快速构建web项目&#xff0c;项目名称为case12-springmvc01。 2.配置Maven依赖 <?xml version"1.0" encoding"UTF-8"?><project xm…...

【React】精选10题

1.React Hooks带来了什么便利&#xff1f; React Hooks是React16.8版本中引入的新特性&#xff0c;它带来了许多便利。 更简单的状态管理 使用useState Hook可以在函数组件中方便地管理状态&#xff0c;避免了使用类组件时需要继承React.Component的繁琐操作。 避免使用类组件…...

VS Spy++进程信息获取

查看进程中窗口信息。 Spy使用介绍 Windows下的程序及热键监视神器——Spy Word进程获取...

Java课题笔记~ SpringMVC概述

1.1 SpringMVC简介 SpringMVC 也叫Spring web mvc。是Spring 框架的一部分&#xff0c;在Spring3.0 后发布的。 1.2 SpringMVC的优点 基于MVC 架构 基于 MVC 架构&#xff0c;功能分工明确。解耦合。 容易理解&#xff0c;上手快&#xff0c;使用简单 就可以开发一个注解…...

SOPC之NIOS Ⅱ遇到的问题

记录NIOS Ⅱ中遇到的报错 一、NIOS II中Eclipse头文件未找到 问题&#xff1a;Unresolved inclusion: "system.h"等 原因&#xff1a;编译器无法找到头文件所在路径 解决方法&#xff1a; 在文件夹中找到要添加的头文件&#xff0c;并记录下其路径&#xff0c;如…...

uniapp uni-datetime-picker 日期和光标靠右

如果想在uni-datetime-picker组件中将日期和光标靠右&#xff0c;您可以使用自定义样式来实现。首先&#xff0c;您需要在页面的样式文件中定义一个类&#xff0c;用于定制uni-datetime-picker组件的样式。例如&#xff0c;你可以在App.vue或者页面的样式文件中添加以下代码&am…...

关于axios请求中的GET、POST、PUT、DELETE的一些认知

这篇写的特别好。而本文主要从实习用途中展开&#xff0c;不专业。 浅谈HTTP中Get、Post、Put与Delete的区别 1、Get 1、目前Get禁止使用requestBody形式传递值&#xff0c;如果使用了&#xff0c;后端会一直报错&#xff0c;让你确认是否有传递参数。 2、举例&#xff0c;模…...

go-zero 是如何做路由管理的?

原文链接&#xff1a; go-zero 是如何做路由管理的&#xff1f; go-zero 是一个微服务框架&#xff0c;包含了 web 和 rpc 两大部分。 而对于 web 框架来说&#xff0c;路由管理是必不可少的一部分&#xff0c;那么本文就来探讨一下 go-zero 的路由管理是怎么做的&#xff0c…...

Springboot集成ip2region离线IP地名映射-修订版

title: Springboot集成ip2region离线IP地名映射 date: 2020-12-16 11:15:34 categories: springboot description: Springboot集成ip2region离线IP地名映射 1. 背景2. 集成 2.1. 步骤2.2. 样例2.3. 响应实例DataBlock2.4. 响应实例RegionAddress 3. 打开浏览器4. 源码地址&…...

智能驾驶系列报告之一:智能驾驶 ChatGPT时刻有望来临

原创 | 文 BFT机器人 L3 功能加速落地&#xff0c;政策标准有望明确 L2 发展日益成熟&#xff0c;L3 功能加速落地。根据市场监管总局发布的《汽车驾驶自动化分级》与 SAE发布的自动驾驶分级标准&#xff0c;自动驾驶主要分为 6 个级别&#xff08;0 级到 5 级&#xff0c;L0 …...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...