最短路径算法

摘要： 随着城市地铁建设的迅猛发展,国内众多城市地铁线路均已实现网络化运营.考虑到地铁票价制定的公益性,目前国内大部分城市均以最短路径或最少车站的方式计算线网两车站间的票价.以传统的Dijkstra算法为基准,对传统的Dijkstra算法进行改进,分别采用传统Dijkstra算法和改进Dijkstra算法对长沙地铁1～5号线线网最短距离行走路线进行测算.结果表明,改进后的Dijkstra算法不仅有效地提高了算法的时效性,克服了传统算法时间冗长的缺陷,在一定程度上消除了线路之间累积的误差且提高了线网的可延展性.

摘要： 本文主要针对穿越沙漠的最短路径问题进行了相关研究,给出沙漠穿越问题的最优解决方案.首先对天气、玩家人数等条件确定的情况下,使用最短路径算法得出最合理的路线,其次得出各种天气状况下各状态(停留、行走和挖矿)的消耗量,最后推断出挖矿过程中的消耗,得出前往终点的最优解.

摘要： 拥堵时段车辆在城市路网中交叉口处的延误甚至会大于其在路段的行驶时间,因而拥堵情况下在城市路网上应用不考虑转向延误的最短路径算法无法反映真实的交通状况.分析既有的考虑转向延误的最短路径算法,扩展网络法因过大的时间和空间开销而欠缺实用性,其余算法包括对偶网络法、节点标号算法和弧标号算法本质均为求包含节点权重和边权重的最短路径问题,最后求解均为节点标号算法.对典型节点标号算法Dijkstra算法进行改进,通过记录节点的紧前节点完成转向判别,并通过最小堆优化将该算法的时间复杂度从O(n2)优化为O(nlogn),并给出算法的数据结构,完成了软件编码,并通过计算实例对算法进行了验证.结果表明:考虑交叉口延误后城市路网最短路径发生变化,同时经过堆优化后算法的时间复杂度下降.

摘要： 本文基于A*算法原理,在Unity3D引擎下,对NavMesh寻路功能进行重新设计优化,并将后续引入到校园场景漫游系统中。

摘要： 穿越沙漠游戏非常有趣,受资金、水、食物及天气的限制,成功完成游戏有一定的困难.本论文根据游戏的不同设定,建立穿越沙漠游戏的数学模型,得到行动路线最优策略.对于第一关,首先,以剩余资金为目标函数,以水、食物及天气为约束条件,分别建立不经过矿山到达终点和途径矿山到达终点的最优策略模型.然后,通过比较剩余资金,得到最优路线为1→5→6→13或1→4→6→13,且在初始起点备54箱水和食物.对于第二关,首先,根据沙暴出现的概率,建立路线分步优化模型,利用决策树算法,得到不同沙暴出现次数的最优策略.最后,给出一般情况下玩家的最佳策略(见表1).

摘要： 电商产业的崛起带动了物流行业的发展,虽然如今的物流行业已有了质的提升,但由此带来的问题也日益凸显,路上的车辆越来越多,越来越拥堵。地下物流系统的发展能有效解决此类问题,同时也符合社会可持续发展的需求。该文主要使用Dijkstra算法,对物流配送路径及节点的选择进行建模分析,求解出配送结点至各需求点的最短路径及所经结点,针对物流节点的选择提供一种行之有效的解决方法。

摘要： 穿越沙漠游戏非常有趣,受资金、水、食物及天气的限制,成功完成游戏有一定的困难。本论文根据游戏的不同设定,建立穿越沙漠游戏的数学模型,得到行动路线最优策略。对于第一关,首先,以剩余资金为目标函数,以水、食物及天气为约束条件,分别建立不经过矿山到达终点和途径矿山到达终点的最优策略模型。然后,通过比较剩余资金,得到最优路线为1→5→6→13或1→4→6→13,且在初始起点备54箱水和食物。对于第二关,首先,根据沙暴出现的概率,建立路线分步优化模型,利用决策树算法,得到不同沙暴出现次数的最优策略。最后,给出一般情况下玩家的最佳策略(见表1)。

摘要： 电商产业的崛起带动了物流行业的发展,虽然如今的物流行业已有了质的提升,但由此带来的问题也日益凸显,路上的车辆越来越多,越来越拥堵.地下物流系统的发展能有效解决此类问题,同时也符合社会可持续发展的需求.该文主要使用Dijkstra算法,对物流配送路径及节点的选择进行建模分析,求解出配送结点至各需求点的最短路径及所经结点,针对物流节点的选择提供一种行之有效的解决方法.

摘要： 随着物联网以及5G技术的普及,传统的网络架构越来越僵化,导致难以部署新的协议;网络虚拟化技术使底层物理网络可以部署虚拟网络,以满足用户的需求。网络虚拟化面临的最大问题在于虚拟网络到物理网络的映射,对此,文章提出一种基于策略网络的虚拟网络映射算法,根据底层物理网络的信息来获得虚拟结点和虚拟链路的映射策略。

摘要： 本文针对Dijkstra算法在处理海量数据时,运算次数随着数据量增大而快速增大,运算效率显著降低的问题,使用最小二叉堆作为Dijkstra最短路径算法的辅助数据结构,有效降低算法的运算次数并提高运算效率.实验选取中国31个省会城市(不包括港澳台)的距离数据和火车直达性数据,数值结果显示采用二叉堆优化之后的算法,求取最短路径的实际时间比传统算法要少,而且随着问题规模的不断增大,两种算法的时间差越来越大,表明二叉堆优化的算法可以显著提高计算效率.

摘要： 为了检验球坐标系中的最短路径算法的计算精度和有效性，本文用Kennett等人(1995)得到的AK135地球速度模型计算全球49种不同的地壳、地幔、地核震相，并与AKI35全球主要震相理论走时表进行对比研究，结果表明:该算法能快速、有效、准确的追踪计算全球常见的主要震相，最大绝对走时误差约为0.1 s，而平均走时误差一般小于0.06 s。因此，该算法可作为区域或全球地震走时层析成像中多震相地震射线追踪计算的一种准确、高效、实用的算法。

摘要： 针对传统串行的最短路径算法的种种弊端本文提出一个可以并行化的最短路径算法,时间复杂度在v个核的处理器上降到0(6nlog2n),明显的提高了程序的执行效率,使用OpenMP实现本算法自动产生多线程自动执行,并给出实例演示算法的执行过程和最短路径树的生成过程,证明算法的可行性。

摘要： 首先介绍智能交通系统的概念及意义,由于ITS在全世界范围内的开展,促使了GIS-T的产生;然后讨论了CIS-T的数据模型;最后根据栅格交通数据模型,提出了一种基于A*思想的栅格最短路径算法。

摘要： 智能交通系统(ITS)是集信息技术、数据通信传输技术、电子传感技术、电子控制技术等为一体的现代交通管理系统.由于ITS在全世界范围内的开展,促使了GIS-T的产生,可以解决最短路径的分析和应用.通过GIS-T的数据模型分析,根据栅格交通数据模型,提出了一种基于A*思想的栅格最短路径算法.

摘要： 针对无向网，采用一维数组对多源最短路径算法进行了改进，将最短路径矩阵中的上三角形区域进行了区域划分，给出了不同区域中一维数组下标计算的递推公式，下标的计算全部转化为简单的加减运算，实验结果表明，该算法与原算法相比，不仅减少了存储，而且提高了运算效率。

摘要： 矿山巷道三维模型能真实地模拟井下的工作场景,基于该模型的网络分析对煤矿井下安全救援十分重要.根据巷道的网络特点,将实际的测量数据中点状和线状元素抽象为节点-弧段图,该图的生成对应着一维中心线和二维双线巷道的构建,在此基础上根据断面的拱高、墙高及拓扑关系进行井巷模型基本单元自动的装配以及三角化生成巷道的三维模型.网络分析采用能适应拓扑变化的Dijkstra算法,从减少搜索节点和采用邻接表的存储结构两方面对传统的Dijkstra算法进行优化,并分析了算法的效率.最后编写程序实现了改进后算法在巷道三维模型中存在障碍的情况下的最短路径分析,并能在三维巷道中漫游显示,结果表明该算法快捷有效.

摘要： 本文研究基于标识站的最短路径算法，实现高速公路联网收费费率生成和车道优惠计算，并通过COM技术实现模块重用。

摘要： 本文从实际应用出发，在RoboCupRescue仿真环境中引入图论算法。分析了大规模城市灾难中警察救援体在交通清理和搜索中的策略。应用最小生成树和最短路径构建城市交通数学模型，辅助警察救援体执行救援任务，为灾难救援提出了新的思路和解决方案。

摘要： 本文针对PDA(个人数字助理)内存资源有限问题，研究发以PDA为平台的最短路径查找算法的优化设计思路，详细阐述了一种基于限制搜索区域的最短路径查找算法。本文从实际应用的角度出发，以市交通道路网为实验数据，并在PDA上实现了本算法。实验结果表明，该算法能够有效的降低时间复杂度，从而减少了路径查找的计算时间，并得到了很好的效果。

摘要： 给出了一种两阶段无线传感器最大生存期消息路由算法,在图建立阶段,从边集中去掉导致刺余能量低于最小剩余能量的边,生成目标图;在路由路径建立阶段,使用加权函数平衡系统最小化能量消耗总和需求和防止传感器能量耗尽的需求,给使用某一路径导致传感器剩余能量变低的边分配较高权值,阻止能导致未来路由失败的边的使用,从而增长了消息的生命周期.实验结果表明本文算法与同类型算法相比,具有网络容量大,消息生命周期长而稳定的优点.

摘要： 本发明涉及防汛信息化及气象应用领域，特别是一种基于最短路径算法的路径相似台风分析方法，该方法通过内插算法，得出每条台风路径中均匀分部的关键路径点，再基于关键路径点，计算出不同台风路径间的最短偏差距离，从而得到地理空间上更为科学的分析最为相似的台风路径，更好的为防汛防台提供科学的技术支撑。

摘要： 本发明公开了一种基于最短路径算法的联盟链通信方法及系统。联盟链中各节点定时向相邻节点发送探测消息，计算网络时延，更新邻居表；各节点定时向相邻节点发送包含自身邻居表的路由消息，交换邻居表信息，更新邻居表；各节点根据邻居表并基于最短路径算法计算自身到联盟链中其他所有节点的最短路径，更新自身路由表；节点发送普通消息时，从路由表中选择目的节点的最短路径发送。本发明设计的方法及系统可以自动寻找最短路径进行通信，且有部分节点宕机或通信链路不稳定时也能够保证链路可用性，冗余消息少，易扩展，通信质量稳定可靠。

摘要： 本发明公开了一种地理分布式云中基于最短路径算法的工作流任务调度方法，该方法能使所有部分的工作流任务的执行时间和执行能耗最少，从而使整个工作流任务的执行时间和执行能耗最优。本发明结合工作流任务的特点和地理分布式云资源的特点提出来基于斐波拉契堆的最短路径工作流任务调度方法。本调度方法适用于地理分布式云中的工作流任务调度，它通过将工作流任务的有向无环图转换为超图，对超图进行划分之后，对每个划分使用Dijkstra算法得出任务执行时间和执行能耗最小的调度方法。这一优化调度方法充分利用了系统资源，缩短了工作流任务的执行时间，最小化了工作流任务的执行能耗。

摘要： 本发明公开了一种用于跳点搜索最短路径算法的矢量地图预处理方法，属于地图搜索技术领域，包括步骤：S1：选取应用需求的精度，将一定范围内的矢量地图转为M*N的网格地图，定义每一个格子为一个基础单元e0；S2：遍历M*N的网格地图，将每k*k个基础单元e0合成为一个单元e1，获得第一层压缩地图，则第一层压缩地图的基础单元e1按规则处理；S3：遍历第一层压缩地图，将每k*k个基础单元e1合成为一个单元e2，获得第二层的压缩地图，则第二层压缩地图的基础单元e2按规则处理；S4：重复步骤S3直至将上一层压缩地图的基础单元合成为一个新单元直至达到满足要求的最大层数，本方案根据使得跳点搜索最短路径算法需要遍历的网格减少，算法执行效率快。

摘要： 本发明揭示了一种基于K最短路径算法的低轨卫星网络路由策略，包括如下步骤：S1、采用随机函数在随机节点上根据时间间隔产生数据包；S2、通过K最短路径算法产生出数据包可走的K条路径；S3、通过最少占用原则在全部K条路径中选择较佳路径；S4、若在较佳路径上发生阻塞，则应用重路由算法，重新通过K最短路径算法计算从当前节点到目的节点的路径，并返回S3；S5、沿路径到达目的节点后，计算系统整体的吞吐量变化。本发明针对低轨卫星网络，提出了一种基于K最短路径策略的改进选路策略，本发明在原有的路径策略上添加了重路由的过程，显著地提高了数据包传输的可靠性，降低了拥塞概率。

摘要： 本发明涉及防汛信息化及气象应用领域，特别是一种基于最短路径算法的路径相似台风分析方法，该方法通过内插算法，得出每条台风路径中均匀分部的关键路径点，再基于关键路径点，计算出不同台风路径间的最短偏差距离，从而得到地理空间上更为科学的分析最为相似的台风路径，更好的为防汛防台提供科学的技术支撑。

摘要： 本发明公开了一种最短路径算法，S1：导入数据，输入各路径节点之间的时间或距离；S2：调用计算机函数，利用编写好的程序进行邻接矩阵的乘法；S3：判断是否已经获得最佳结果，如是则结束算法，输出最短路径；如还不是最佳结果则还继续乘邻接矩阵，直到获得最佳结果为止。本算法功能性强，适用范围广，可以算出全局最短路径，也可以算出规定了起点或者终点的最短路径问题，适用于有负赋权的最短路径问题，还可解决任意两点之间至多经过任意有限个中间点的最短路径问题；还可以解决动态图的最短路径问题；本算法计算原理直观，易于理解。综上，本算法扩展能力强，经过改进可以解决多种特定条件下的最短路径问题。由于本算法类似于矩阵乘法运算，可以借鉴稀疏矩阵的算法，降低时间复杂程度。

摘要： 本发明公开一种基于最佳适应和最短路径算法的虚拟网络资源分配方法，其实现步骤为：构建每个用户的虚拟网络，采用最佳适用算法，将每个虚拟网络中的每个虚拟节点映射到物理网络的一台服务器上，采用最短路径算法，将每个虚拟网络中的每条虚拟链路映射到物理网络服务器之间的一条路径上，该路径为虚拟链路的两个虚拟节点分别映射到的服务器之间的最短路径，将映射完成后服务器承载的所有虚拟节点作为虚拟网络资源的分配结果，使得本发明虚拟网络资源分配占用的服务器个数尽可能的少，从而提高了虚拟网络的接收率，降低了数据中心的系统能耗。

摘要： 本发明公开了一种基于最短路径算法的联盟链通信方法及系统。联盟链中各节点定时向相邻节点发送探测消息，计算网络时延，更新邻居表；各节点定时向相邻节点发送包含自身邻居表的路由消息，交换邻居表信息，更新邻居表；各节点根据邻居表并基于最短路径算法计算自身到联盟链中其他所有节点的最短路径，更新自身路由表；节点发送普通消息时，从路由表中选择目的节点的最短路径发送。本发明设计的方法及系统可以自动寻找最短路径进行通信，且有部分节点宕机或通信链路不稳定时也能够保证链路可用性，冗余消息少，易扩展，通信质量稳定可靠。

摘要： 本发明公开了一种X射线透视图像下基于深度分割网络和最短路径算法的导丝分割方法，该方法构建了深度分割网络OCR U‑Net以及Dijkstra最短路径算法，得到X射线透视图像下导丝分割模型。首先训练X射线透视图像导丝分割模型，得到每个像素属于导丝的概率值，然后用得到的逐像素概率值与该位置的灰度值加权求和作为距离，最终使用Dijkstra最短路径算法优化导丝分割结果。本发明能自动、完整地分割X射线透视图像下的导丝结构。