最短路问题的Floyd加速算法与优化

Floyd算法是求解网络中任意两点之间最短路的高效算法,文章给出了在不含负回路的网络中Floyd加速算法及优化方法,并构造了求解最短路径的序号矩阵。算法分析和计算实例表明,优化后的Floyd加速算法迭代速度快,计算量大大减少,路径寻找简单、直观。     

基于神威平台的Floyd并行算法的实现和优化

求解全源最短路径的Floyd算法是许多实际应用基础上的关键构建块,由于其时间复杂度较高,串行Floyd算法不适用于大规模输入图计算,针对不同平台的并行Floyd算法设计可为解决现实问题提供有效帮助.针对Floyd算法与国产自主研发处理器匹配滞后的问题,首次提出基于神威平台的Floyd并行算法的实现和优化.根据SW26010处理器主-从核架构的特点,采用主从加速编程模型进行并行实现,并分析了影响该算法性能的关键因素,通过算法优化、数组划分和双缓冲技术进行优化,逐步提升算法性能.测试结果表明,与主核上串行算法相比,基于神威平台的Floyd并行算法在单个SW26010处理器上可以获得106倍的最高加速.     

一类标准矩形网络节点间最短路径的求解方法

针对常见的交通道路最短路径问题, 提出标准矩形网络的概念, 分析其节点间最短路径的性质, 并在此基础上给出一种新颖的最短路径求解算法. 该算法利用标准矩形网络的几何性质, 简化了搜索方向和步长的判断, 同时指出常见的交通道路网络一般均可以整体或部分化为标准矩形网络. 与常见的求取最短路径的Dijkstra、Floyd、ACO、A* 等算法进行仿真实验比较, 实验结果表明, 对于大规模标准矩形道路网络, 所提出算法具有更好的寻优精度、稳定性和寻优速度.

     

基于图论的物流配送最短路径比较研究

通过实例对比分析Dijkstra算法和Floyd算法特点及适用性,选用Dijkstra算法计算物流配送的最短路径,给出Dijkstra算法求解最短路径问题的实现方法及步骤并集成了一个小型系统,使用随机生成的数据进行最短路径求解,将生成的最短路径在随机生成的图上进行演示,并计算出两种算法执行时间,以期对物流配送中点对点的最短路径有所帮助。     

基于Floyd算法的多重最短路问题的改进算法

路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。     

Floyd算法的景区最短路径查询系统的设计与实现

介绍一个基于改进的Floyd算法，并综合运用C语言文件操作技术和编程技术设计并实现了一个景区景点之间的最短路径查询生成系统，反映了路径上前后两个景点的先后关系，克服了经典Floyd算法只给出了路径上所经过的景点，而没有反映出景点之间的先后关系的不足.     

有向赋权网络中任意节点对的最短路径集求解方法

有向赋权网络任意节点对之间的最短路径可能多于一条,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,向其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的路径,通过与前次Floyd算法计算出的最短路径进行比较,筛选出构成最短路径的所有中间节点,并构建路径支撑树,基于路径支撑树确定任意节点对的最短路径集.     

基于半空间的最短路径算法模型研究

目前在GIS领域,对最短路径搜索问题的研究和应用较多,其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题.通过对基于Dijkstra最短路径搜索算法的优化途径的分析,提出了基于半空间的最短路径算法,并在VC 环境下设计相应的程序验证了此算法.应用该算法开发了"焦作市地理信息公共查询系统"系统,取得了比较满意的效果.     

改进Dijkstra算法在GIS导航应用中最短路径搜索研究

研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。     

两种最短路径算法的比较

Dijkstra算法与Floyd算法是求最短路径的最常用、也是最有效的两种方法。通过从多方面对Dijkstra算法与Floyd算法的进行比较、分析,给出这两种算法的差异及Floyd关键部分的程序,并介绍了Dijkstra改进的算法。     

最短路问题的Floyd改进算法

目前在不含负回路的网络中,对于求解任意两节点之间最短路问题的方法有很多,Floyd算法是最经典的算法之一,但随着节点数量的增加,重复的计算量也随之增大,从而降低了计算效率。为此,文中通过迭代矩阵和下标标注法对Floyd算法进行了改进,改进后的算法既能快速地计算出网络中任意两节点之间的最短路长值,又能更直观地找出最短路径。通过具体实例分析表明,Floyd改进算法减少了重复计算,简化了路径标注方法,提高了计算效率。     

基于小世界的无线传感器网络的路由算法

针对小世界的拓扑特性,提出一种基于小世界的无线传感器网络(WSN)的路由算法。该路由算法引入超级节点环概念,将超级节点环视为无向图,利用改进的Floyd算法计算出最短传输路径,缩短路由建立时间,进而提高网络的传输效率,降低无线传感器网络的能耗。仿真结果表明,该算法与针对小世界提出的路由算法PSCF、SWRP和MH相比,在路由建立时间、能量消耗和网络吞吐量方面效果显著。     

Dijkstra, Floyd and Warshall meet Kleene

Around 1960, Dijkstra, Floyd and Warshall published papers on algorithms for solving single-source and all-sources shortest path problems, respectively. These algorithms, nowadays named after their inventors, are well known and well established. This paper sheds an algebraic light on these algorithms. We combine the shortest path problems with Kleene algebra, also known as Conway’s regular algebra. This view yields a purely algebraic version of Dijkstra’s shortest path algorithm and the one by Floyd/Warshall. Moreover, the algebraic abstraction yields applications of these algorithms to structures different from graphs and pinpoints the mathematical requirements on the underlying cost algebra that ensure their correctness.     

一种基于边序列的任意两点间最短路径算法

基于边序列信息,论文提出了一种新的求取任意两点间最短路径的算法:EBSP(EdgesBasedall-pairsShortestPathsAlgorithm)。该算法在算法时间复杂度上同Floyd算法相近,并在一定条件下相同;通过试验表明,在边数m满足m=c*n的情况下,EBSP算法速度约为Floyd算法的10倍到63倍。     

A Two-Criterion Lexicographic Algorithm for Finding All Shortest Paths in Networks

An algorithm for finding all shortest paths in an undirected network is considered. The following two criteria are used: the minimum number of arcs in a path and a minimum path length. The algorithm is analyzed for complexity, and it is empirically shown that, with increasing the network density, its computational efficiency becomes higher than that of the Floyd algorithm adequately modified to find the shortest path with the use of a two-step criterion.