Day 65 || SPFA、判断负权回路、bellman_ford之单源有限最短路

news/2024/11/16 9:20:44/

算法-又名spfa">Bellman_ford 队列优化算法(又名SPFA)

题目链接:卡码网:94. 城市间货物运输 I

思路:具体参考“代码随想录——Bellman_ford 队列优化算法(又名SPFA)”,主要的思想是在Bellman_ford算法中因为要每条边都要松弛(判断是否可以松弛),但是改进队列优化使用了邻接表先查询到当前点邻接的是什么点然后放入队列遍历松弛,节省遍历所有路径判断是否可以松弛这个步骤,节省时间。但是是有弊端的,一方面队列读取存储耗时,另一方面如果路径过多其实理论时间上无限接近于“Bellman_ford ”算法

bellman_ford之判断负权回路

题目链接:卡码网:95. 城市间货物运输 II

思路:判断是够有负权回路有两种方法,第一种以为我们知道如果没有负权回路的话Bellman_ford原始方法不断松弛即使n次以上minDist也不会变化,因为路径已经是最小的了,但是负权回路会使得minDist不停变小。第二种方法是Bellman_ford 队列优化算法下,已知每个店最多会被加入队列n-1次,但是超过n-1那必然是负权回路。(具体参考“代码随想录——bellman_ford之判断负权回路”)。

bellman_ford之单源有限最短路

题目链接:卡码网:96. 城市间货物运输 III思路:k个城市就是松弛k+1次,讲解了录入路径的顺序对之后的遍历也会有影响所以不能完全相信k+1次松弛,所以每次松弛需要保存上一次松弛的结果进行对比。(具体参考“

代码随想录——bellman_ford之单源有限最短路

”)


http://www.ppmy.cn/news/1547418.html

相关文章

自定义实体类中DateTime属性的序列化格式

目录 一、Newtonsoft.Json下自定义DateTime序列化格式器 1. 定义DateFormatConverter 2. 在实体上使用自定义的DateFormatConverter特性 二、System.Text.Json下自定义DateTime的序列化格式器 1. 定义DateTimeConverter 2. 定义DateTimeJsonConverter特性 3. 在实体上使…

谷歌Gemini发布iOS版App,live语音聊天免费用!

大家好,我是木易,一个持续关注AI领域的互联网技术产品经理,国内Top2本科,美国Top10 CS研究生,MBA。我坚信AI是普通人变强的“外挂”,专注于分享AI全维度知识,包括但不限于AI科普,AI工…

数据结构Python版

2.3.3 双链表 双链表和链表一样,只不过每个节点有两个链接——一个指向后一个节点,一个指向前一个节点。此外,除了第一个节点,双链表还需要记录最后一个节点。 每个结点为DLinkNode类对象,包括存储元素的列表data、…

Vue3中一级导航栏的吸顶导航交互以及Pinia优化重复请求

一、前言 在日常的网站中,当鼠标滚轮往页面的底部滑动时,会出现顶部导航栏的隐藏,而出现新的导航栏显示,这就是一级导航栏的吸顶导航交互。本文当实现改模块功能的实现。 二、示例图 参考黑马程序员小兔仙儿PC端项目:…

CSS回顾-颜色单位详解

一、引言 在网页设计中,颜色至关重要。CSS 丰富的颜色单位如同调色盘,开发者用它为网页元素上色。从易记的颜色名称、精确的十六进制值,到光学原理相关的 RGB、HSL 模型,各颜色单位都有独特用途。理解和运用这些单位是打造吸引人…

自动化爬虫Selenium

自动化爬虫Selenium 这篇文章, 我们将要学习自动化爬虫的知识啦。 目录 1.Selenium的基本操作 2.用Selenuim获取数据 3.当当网数据获取 4.实战 一、Selenium的基本操作 首先, 我们在使用Selenium之前, 需要做两件事情。第一件事情, 就是安装第三方库, 第二件事情, 就是…

blockchain实现遇到的问题

区块链分叉 v1114 : 基于python socket 创建TCP server,以中心化的形式暂时实现区块链的状态同步 C:\Users\vin0sen>nc 192.168.137.1 9000 Enter a new data: 111 {"index": 1, "timestamp": "2024-11-14 15:28:53.173112", &quo…

「AI Infra 软件开源不是一个选项,而是必然」丨云边端架构和 AI Infra专场回顾@RTE2024

在人工智能和开源技术蓬勃发展的当下,AI Infra 项目正经历着日新月异的变革。从跨平台运行时到云边端 AI 基础设施,再到多模态知识助手,创新浪潮席卷而来。这些进步不仅显著提升了技术指标,也为实时音视频处理、边缘计算、大模型应…