基于可行路径最短路径的一种算法

研究无向连通图最短路径的一种算法.此算法比Dijkstra算法和Floyd算法更具有实用性,能够给出图中任意两个顶点间的最短路径序列、任意两个顶点间的最短路径及任意两点间的所有可行路径的长度.     

复杂路网下多客户间最短路径的扇面Dijkstra算法

复杂路网模型下多客户之间最短路径的计算,直接影响市区集送货问题的求解效率。该文提出多客户间最短路径扇面Dijkstra算法。该算法首先由客户在路网的分布确定出最小扇形区域及扇面搜索区域,并将路网节点分为拓展点集、邻节点集。然后在搜索过程中通过优化到达邻节点的通行代价来确定新的拓展点集、邻节点集。算法通过限制搜索区域、减少遍历节点的数量来缩短搜索时间。100个分布于北京市的客户间最短路径的计算表明,相对于Dijkstra算法,扇面Dijkstra算法能够在保证精度的前提下,降低15%的最短路径求解时间。     

稀疏网络的Floyd动态优化算法

通过对Floyd算法进行研究,提出了一种新的求取任意两点间最短路径的算法:Floyd动态优化算法.该算法通过引入插入数组、可达数组以及可发数组,使得算法在求解最短路径前自动修改能够最小化路径的节点,剔除一些无用的节点,最小化语句执行的次数.算法分析表明,新算法在稀疏网络中比Floyd算法在性能上有较大的提高.     

大规模网络最短路径算法的优化及实现

求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题．在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法．初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80％,在耗费的存储空间上减少了将近一倍．     

路网车流径路优化调整中的最短径路算法

目前铁路车流径路基本上都是按照路网的最短路径来安排的,首先一般都采用Dijkstra算法计算最短路径,然后参考相应区段的能力限制,对车流进行分配,对车流量超过能力的区段重新进行车流调整,这时需要重新计算新条件下两点间最短路径,一般仍采用Dijkstra算法重新计算两点最短路径,这大大地浪费了前期的计算最短路径的信息,增加了计算工作量,本文采用A*算法作为一种启发式算法,可以克服这一缺陷。     

适用于大规模网络的全源最短路径重优化算法——RASP算法

为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.     

动态速度和代价约束的最短路径算法

Dijkstra算法是计算有向图中一个节点到其余各个节点最短路径的著名多项式时间算法,在交通规划、地理信息系统等方面有重要的应用。本文改进Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径,即有向图的节点之间除了静态的距离外,还有动态的速度和代价,例如城市交通中的高峰与非高峰时段影响速度/时间,收费与非收费路段影响代价;时间和代价在最短路径中由一个比例因子控制,通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的,实验结果也表明了该算法的有效性。     

一种基于Dijkstra算法的三角网格地表模型算法

对二维地表模型运用Dijkstra算法求解最短路径时,为了减少计算量,需要对模型进行简化后,才开始进行Dijkstra算法的求解,所以结果并不符合实际地表情况。不在模型上进行任何简化,而是直接在模型上划分三角网格来处理最原始的模型。然后用基于Dijkstra算法和矢量夹角的三角网格地表模型算法求解最短路径。通过此算法完成了一个实例的最短路径求解。结果表明,采用文中算法所得到的结果符合Dijkstra算法求得的路径和实际情况,而复杂度并没有因为未简化模型而大幅上升,并且算法具有效率高、复杂度低、稳定性好等优点。     

网络最短路径算法的改进及实现

从节约存储空间和提高运算速度方面对Dijkstra最短路径算法进行了改进．定义新的节点类来高效存储网络的拓扑信息。节省了计算机存储空间；采用满二叉堆数据结构对节点进行排序并选取最短路径节点。大大提高算法效率，仿真例子表明．对于某些网络结构．改进算法能把传统Dijkstra算法的时间复杂度由原来的O(N^2)近似降至o(N)。     

Floyd算法的改进与优化

介绍一个改进的Floyd算法。本文综合运用C＋＋语言编程技术,设计并实现了求带权有向图中各个顶点之间最短路径的算法,反映了最短路径序列上前后两个顶点之间的先后关系。本算法从顶点出发,每次在求各顶点间最短路径的时候,都进行路径优化。改进后的Floyd算法,迭代速度快,计算量一定程度减少。     

赋有权向量网络的字典序最短路

本文以多目标优化设计为背景,提出了赋有权向量网络的字典序最短路概念。在字典序极小的意义下,推广了最短路问题的Dijkstra算法和Floyd算法,讨论了算法的复杂性,为一类问题的多目标优化决策提供了一种工具。     

实际配送中多个配送点闭回路最短路径的选取

将Dijkstra算法与Kruskal算法相结合求由配送中心到多个销售点然后返回配送中心最短的闭路径,比单一的用Dijkstra算法和Floyd算法简单,比单一的用Kruskal算法精确,从而给实际计算带来方便。     

Floyd—Dijkstra算法在电缆敷设设计中的应用

通过将Ｆ－Ｄ算法应用于电缆敷设设计中,提供一种实现电缆敷设的优化设计的方法,并用实列进行验证。     

网络优化中最短路问题的改进Floyd算法

在Gauss-Seidel迭代法思想的基础上,提出了一种改进的Floyd算法来计算任意两点之间的最短路问题。通过对带权邻接矩阵按照行列由小到大和由大到小的顺序进行计算,只需两步迭代求得最短路长。算法分析和计算实例表明,改进的Floyd算法大大减少了迭代次数,提高了算法效率。     

应急资源配送中Dijkstra改进算法的研究

路径规划问题是应急资源配送中的核心问题,最短路径算法在路径规划过程中起着决定性的作用,在众多路径规划算法中最经典且最具代表性的就是Dijkstra算法。以传统的Dijkstra算法分析为基础,从存储结构和算法过程两个方面进行一定程度的改进,目的是在节点数和边数较多的情况下,提高网络模型的处理效率。以真实道路交通数据为基础进行相关实验,结果证明,改进后的Dijkstra算法可以有效减少节点的计算量,提高算法的运行效率。     

空间分析中双向Dijkstra算法优化研究

在分析现有双向Dijkstra算法基础上,通过调整搜索规则,提出了一种改进的用中间链表加速的双向Dijkstra算法,保证了前向和后向搜索在中间相遇,大大地节省了算法的运行时间.经验证,算法的运行效率比传统Dijkstra算法平均提高90%.     

一种改进的基于无链表SPIHT的图像压缩算法

 SPIHT算法以其简单高效而著称,但由于LSP、LIP和LIS 3个链表的使用,内存需求量大,且需要动态分配或删除链表节点;另外,排序阶段存在的重复扫描也严重影响了算法的效率和性能,因此算法不易在硬件平台上实习,也不适用于低内存和实时应用场合。本文针对SPIHT算法的不足,提出了一种改进的无链表SPIHT算法。首先,在排序阶段加入对A类集合的分类判断,优化了码流输出,提高了压缩性能;其次,在存储重要信息时,算法以状态标识矩阵代替链表,既节约了内存开销也避免了内存的动态管理,最大输出位数和集合极值矩阵的使用则减少了扫描次数,提高了运行效率。     

基于预处理的点到点最短路径计算方法

基于经典的Dijkstra算法,研究采用预处理的点到点最短路径算法。通过引入双向Dijkstra和基于reach的预处理方法形成新的RE算法,并利用C++编程设计算法程序,将新算法应用于交通工程领域。利用EFSS数据结构搭建考虑交叉口和路段延误的交通网络,检验新算法的适用性和效率,结果发现RE算法与Dijkstra算法相比,搜索速度有大幅提升且能保证路径查询的正确性,RE算法在大规模网络上优势更为显著,查询时间约为Dijkstra算法的10%。