当前位置: 首页 > 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 …...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...