Dijkstra算法中的多邻接点与多条最短路径问题

Dijkstra算法是图论中求取最短路径的经典算法。列举并分析了Dijkstra算法及其伪码,为了深刻理解Dijkstra算法,列举了几种错误观点并加以纠正。分析发现,根据Dijkstra算法,最短路径上的某个顶点的前面,可能有多个邻接点;从开始点到某个顶点之间,可能存在多条权重相同的最短路径。对于上述多邻接点问题与多条最短路径问题,Dijkstra算法并没有涉及。分析了多邻接点问题与多条最短路径问题的成因,提出解决方案,对Dijkstra算法进行了改进,给出了改进之后的算法与伪码,分析了算法的时间复杂度,并用c语言编码实现。实验结果表明,改进之后的Dijkstra算法可以有效解决多邻接点问题与多条最短路径问题。

一种实用的所有点对之间最短路径并行算法

针对有向图中每对顶点之间的最短路径问题,在基于扩充了路径矩阵的串行Floyd算法上,提出了二维网格结构上的并行算法。选用的任务划分方法为二维均匀块分配方法。该并行算法已经在NOW上的MPI平台上实现,理论分析和数值实验表明它具有较高的扩展性和并行效率。

剩余最短路径算法应用于起迄点交通调查统计

从研究旅行者的出行行为特征出发,并结合道路网拓扑关系,提出一种全新的剩余最短路径算法,用于起迄点交通量调查统计.对于每个起迄点对,先找到连接这个起迄点对的最短路径,再把这个路径上调查到的交通量从路段上转移到该起迄点对上.再寻找剩余的下一个最短路径,也把相应的路径调查交通量从路段上转移到起迄点对上.这样重复下去,直到该起迄点对的交通量全部从调查路段上转移至起迄点对.该方法可以有效解决交通出行被重复统计和被遗漏的情况,还可以为今后的起迄点调查提供更合理的测点.

必经点最短路径问题模型及相应遗传算法研究

根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型。以分类保序最短路径为例,设计相应的改进遗传算法。该遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群。通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度。仿真结果验证了算法的有效性。

基于点割集的并行最短路径算法

在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.

基于几何特征枝干点云骨架提取最短路径算法

树木建模广泛应用于林业信息化等领域,点云各项优良特性使其也称为树木建模主要方法。基于几何特征的树木枝干点云骨架提取中以根节点距离相似归类的方法在枝条分叉处更加合理,而该方法的实际应用受制于传统使用的最短路径求解算法的Dijkstra算法因而较少。主要针对树木枝干点云,将现有若干最短路径算法进行相应的改进以应用于基于几何特征的树木枝干点云骨架提取中。通过实际数据验证可知,利用邻接表能够大幅度降低内存需求,相较于以往采用的Dijkstra算法,SPFA的执行速度是理想的,更加快速,能够对精细化点云树木建模提供帮助。

城市交通中结点约束的动态最短路径查询算法

城市交通中道路拥堵情况多变,在车辆行进过程中两点间最短路径会发生改变。文章提出基于Dijkstra的动态更新算法,同时考虑必经结点对算法的影响,计算复杂度大大降低。文中给出了算法的理论依据,处理过程及最终效果图。

单源点最短路径动态优化算法

设计了最短路径时间复杂度取决于边数e和点数n的动态优化算法。采用了独特的动态PV集合链,改进了当前求得的最短路径向量D的存储结构,用PV集合链对向量D进行动态管理,使其时间开销为e+(n-1)×(n-2)/2+3n。当n>4时,SPD OA算法的性能明显优于Dijkstra算法,呈现出良好的动态优化特性。最后对动态优化算法与Dijkstra算法用理论公式得出的数据进行了时间性能比较。

基于最短路径和样点插值的城市基准地价GIS系统

研究并介绍了几种主要的基准地价测算方法,其中样点法是一种快速直观、现势性好的新方法;样点法通常需要基于最短路径来进行.本文对传统的最短路径方法进行了补充,计算得到了更为精确的空间任意两点之间的最短距离,提高了地价衰减模型的计算精度;基于最短路径计算结果,采用移动平均法进行空间插值,设计并实现出相应的G IS系统,应用于实际的基准地价计算与结果表现.

超立方体中过k个指定点的最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(k<n)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n^2+2n(n^2+2)次运算,算法的时间复杂度为O(n^3),属于多项式计算.

一种求解点到点的最短路径的高效下界算法（英文）

在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题.学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等.这些算法所使用的距离估值比较松散,仍然有很大的提升潜力.ACT算法是一种新的两阶段目标制导下界算法,它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识.新算法充分利用了预处理数据,可以获得非常好的距离下界.在真实路网上的实验结果表明,新算法的性能明显优于以往的算法.在某些实例下,最优版本的ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25%左右.

超立方体中最短和次短的点不交路径

n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响。本文研究n维超立方体Qn的最短路径问题,采用构造的方法证明了以下结论: Qn中任意两点之间一定存在k条不交的长度为k的最短路径,其中k为此两点之间的Hamming距离。此外,如果放宽最短路径的条件,对两点之间的 Hamming 距离为k的点,长度最多为k+2的不交路径存在至少n条。

过必经点集且具有额外硬约束的最短路径算法

求解过必经点集的最短路径问题已有多种算法,但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题,提出一种基于深度优先搜索发展的随机搜索算法,由使用者依据现场情况给出数学描述,建模抽象为无向带权图表示;依据路径规划要求定义相关变量,包括路径规划的起点、终点、必经点集以及额外硬约束条件,图信息和节点信息以邻接矩阵的形式保存;搜索过程中对路径的可行性加入额外硬约束条件进行实时判定,最终获得最短路径解。实验仿真和实测结果表明,该算法能有效规避额外硬约束条件下的中间路径,生成合理的最短路径,改善相关问题的可求解性。

基于抛弃结点法实现铁路客货运最短路径计算

使用普通网络拓扑结构的迪杰斯特拉算法在计算铁路客运、货运最短路径时,由于结点多而浪费内存空间,增大运行时间,降低运行效率。针对这一现象,提出一种抛弃结点法的存储方式,把出入度等于2的结点抛弃掉,更新网络拓扑图。结果表明,该算法在实现铁路客运、货运最短路径时,极大地缩短了算法运行时间,提高了运行效率。

基于最短路径的GNSS-R镜面反射点算法

提出一种基于最短路径的全球导航卫星系统反射信号(global navigation satellite systems-reflectometry,GNSS-R)镜面反射点算法。首先,在卫星发射机与接收机形成的线段上,插入该线段二分点以及由发射机、地球球心与接收机3点所形成角的角平分线与发射机与接收机形成线段的交点;其次,计算并比较上述2点星下点的反射路径长度,保留较短反射路径长度;最后,在给定的精度范围内找到最短反射路径,确定镜面反射点。仿真实验结果表明,与Gleason算法和线段二分法相比,提出算法的收敛迭代次数较低,准确性较高。

求所有最小点成本最短路径算法

对点带成本的最短路径问题进行了研究。根据点带成本最短路径问题特点,对Dijkstra算法进行修改后给出一个时间复杂度为O(|V|2+|E|)、空间复杂度为O(|V|+|E|)的算法,并在此基础上充分利用问题的特点,给出一个时间复杂度为O(w|V|)、空间复杂度为O(|V|+|E|)、构造所有点带成本最短路径的算法。

基于有效拐点和最短最小路径的蚁群路径规划方法

为了提高蚁群算法路径寻优的收敛精度和收敛速度,提出一种基于有效拐点的栅格图和基于最短距离最小步数路径(最短最小路径)的蚁群算法,用于搜索地面移动机器人从起点到终点的最短路径。在标准蚁群算法路径规划中,蚂蚁的搜索方式是有限方向有限邻域,本文采取无限邻域的搜索方式,可取捷径搜索任何可直通的栅格点,并提出有效拐点的概念,减小了单步搜索量。提出最短最小路径的概念,并用其取代欧氏距离作为启发值,提高了启发值的准确度和可靠性,同时用起点到终点的最短最小距离指导信息素更新,提高了蚁群算法迭代的质量。最后,在不同规模、不同障碍比例的栅格地图环境下进行实验,结果表明用最短最小路径距离取代欧氏距离的合理性,并验证了本文方法可以在降低计算量的同时,以更快的收敛速度搜索到距离更短、步数更少的路径。

必经点约束型最短路径问题的研究

为了解决网络路由中带有必经点约束的网络拓扑中最优路径的问题,提出了采用改进的蚁群算法和Dijkstra算法对最优路径进行规划。首先,针对含有必经点约束的问题,在信息素初始化时增加在必经点上的信息素。其次,为了能够更好地找到最优解,采用了狼群分配算法进行信息素更新,提高了收敛速度,并且采用了Dijkstra算法对蚂蚁找到的最优路径进行二次优化。最后,分别用不同节点和必经点规模的网络进行实验,并与基本的蚁群算法进行了比较,证明了改进蚁群算法的正确性和高效性。

基于Dijkstra的多源点最短路径求解算法的设计与分析

Dijkstra是图的单源点最短路径算法,本文介绍利用Dijkstra算法进行多源点最短路径求解的方法,不仅能统计任意两点间的最短路径长度,而且能够求解两点间的具体路径并以堆栈显示,因此有助于算法的学习、比较及拓展,提高计算思维能力。

结点有拥塞的动态最短路径问题的算法研究

最短路径问题在交通运输领域以及网络路由选择方向都有着重要的应用.本文在有必经结点且所经结点无序的最短路径算法的基础上,研究结点有拥塞且拥塞程度是动态变化的最短路径问题.对于这种情况的研究,在交通运输领域的高速公路以及局域网络上的路由选择都有着重要的应用.文中对结点的权值,即拥塞程度的预测采用了Kalman滤波方法,并用改进了的Dijkstra算法求解结点间的最短路径.相关实验结果及分析表明,该方案可以有效地解决结点有拥塞且拥塞动态变化的最短路径问题.