首页 > 编程语言 >分布图最短路径算法比较

分布图最短路径算法比较

时间:2024-01-23 15:45:42浏览次数:28  
标签:路径 分布图 最短 算法 时间 加载

用户维护好仓区的点和线,生成分布图时,用户任意选取两个点,后端求出当前最短路径。

假设图G(m, n),m个顶点,n条边

算法对比:

  1. floyd算法
    时间复杂度o(m3)
    缺点:时间复杂度过高
  2. dijkstra算法
    时间复杂度o(m2),使用优先队列可以降到o(m * logm)
    邻接矩阵存储:适合稠密图
    邻接表存储:适合稀疏图
    缺点:不适合负权场景

项目业务场景不存在边为负权,并且大部分为稀疏图,所以采用dijkstra算法,使用邻接表存储各个节点离初始点的最短距离,通过给点增加前置节点属性保存最短路径轨迹


使用优先队列对比测试(空间换时间)

图G(7,10)

代码预热后测试(类加载是按需加载,第一次跑会进行类加载过程,会消耗较多时间,所以先空跑两次预热后再进行时间的统计):

调用次数 10 1000 2000
优化前消耗时间 1ms 28ms 35ms
优化后消耗时间 <1ms 12ms 15ms

标签:路径,分布图,最短,算法,时间,加载
From: https://www.cnblogs.com/zhengbiyu/p/17982616

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt (185)-- 算法导论14.1 2题
    二、用go语言,对于图14-1中的红黑树T和关键字x.key为35的结点x,说明执行OS-RANK(T,x)的过程。文心一言:在红黑树中,OS-RANK(T,x)是一个操作,用于计算节点x在红黑树T中的秩。秩是一个节点的相对高度,对于根节点,其秩为0。首先,我们需要明确红黑树的性质:每个节点要么是红色,要么......
  • 文心一言 VS 讯飞星火 VS chatgpt (185)-- 算法导论14.1 2题
    二、用go语言,对于图14-1中的红黑树T和关键字x.key为35的结点x,说明执行OS-RANK(T,x)的过程。文心一言:在红黑树中,OS-RANK(T,x)是一个操作,用于计算节点x在红黑树T中的秩。秩是一个节点的相对高度,对于根节点,其秩为0。首先,我们需要明确红黑树的性质:每个节点要么是红色......
  • 读论文-基于注意力机制的对抗性协同过滤推荐算法
    前言今天读的论文为一篇名叫《基于注意力机制的对抗性协同过滤推荐算法》,文中主要介绍了一种基于相关注意力的协同过滤推荐算法,该算法结合深度学习中的注意力机制为不同物品分配不同的权值来捕获与目标物品最相关的物品,探索不同物品的权重对模型预测的影响并以此提升推荐的准确......
  • 算法学习Day38斐波那契数、爬楼梯
    Day38斐波那契数、爬楼梯ByHQWQF2024/01/22笔记509.斐波那契数斐波那契数,通常用 F(n)表示,形成的序列称为斐波那契数列。该数列由 0和1开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1) =1F(n)=F(n-1)+F(n-2),其中n>1给你n,请计算F(......
  • 算法学习Day39不同路径
    Day39不同路径ByHQWQF2024/01/22笔记62.不同路径一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?示例1:输入:m=3,n......
  • 算法学习Day41整数拆分、不同的二叉搜索树
    Day41整数拆分、不同的二叉搜索树ByHQWQF2024/01/22笔记343.整数拆分给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例1:输入:2输出:1解释:2=1+1,1×1=1。示例 2:输入:10输出:36解释......
  • 《算法引论》第二章(数学归纳法)
    第二章总结2.1原始的数学归纳法可以变形为各种形式,核心是有几个知道的n比较小的值或者性质+有一些从前向后的推断方式,然后推出一系列东西。比较常见的变形有强归纳法、间隔归纳法(n=1,2,..k时成立,n-k成立能推出n成立)、指数归纳法(n/k推n),等等。关键:根据我们掌握了什么决定使用什么......
  • 算法学习Day37单调递增的数字
    Day37单调递增的数字ByHQWQF2024/01/22笔记738.单调递增的数字给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。(当且仅当每个相邻位数上的数字 x 和 y 满足 x<=y 时,我们称这个整数是单调递增的。)示例1:......
  • 机器人的控制算法(传统控制算法、基于模型的控制算法、非人工智能算法) —— 自动控制算
    参考:https://careers.tencent.com/jobdesc.html?postId=1742828601499197440机器人算法:机器人算法在AI领域兴起之前其实就是指自动控制算法,但是自动控制算法只能解决简单场景环境下的控制问题,对于复杂场景下自动控制算法往往效果有限,而复杂场景下使用AI算法来进行控制会得到......
  • 算法基础_1
    title:(算法基础课)link:(https://www.acwing.com/)cover:(https://cdn.acwing.com/media/activity/surface/log.png)上课理解思路->下课理解背过代码模板->做3-5遍题目(循环AC)排序快速排序快速排序模板题例题分治:用一个数来分,不需要必须是中心数先分完再递归两边......