最短路问题的Floyd改进算法

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

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

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

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

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

基于MATLAB求解任意城市间的最短路问题

本文首先介绍最短路问题的数学模型及Dijkstra算法，紧接着采用Dijkstra算法的改进算法——Floyd算法，然后将求城市道路网两点间最短路径目标约束转化为求最短路问题．随之建立最短路模型，并描述了用MATLAB程序进行求解的过程。最后用实例验证了模型和算法的可用性。     

闭合螺线阵列的最短路径算法

介绍了闭合螺线阵列的概念;利用动态规划法中的Floyd算法思想对求解闭合螺线阵列最短路径的问题进行了描述,并给出了具体算法;给出了利用二维数组算法求解闭合螺线阵列最短路径的过程.对于以上两种算法的优缺点进行了比较.这两种算法可以用于解决大多数路径问题.     

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

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

智能交通中的高效多准最短路径混合算法*

针对智能交通系统（ITS）中求解多条准最短路径的问题,提出了一种混合算法。该算法以Floyd算法和A*算法为基础,主要运用遗传算法来求解多条准最短路径。实验的结果表明了该混合算法的可行性和比其他算法的高效性。     

大规模定量传输的时间扩展网络K最短路径算法

大规模的军用物资调度,需要传输的物资远远超出保障网络实际传输能力的情况下,现有的Dijkstra算法、Floyd算法以及传统的网络K-最短路径算法,难以求解这类网络调度优化问题。在蚁群算法的基础上,设计了一种基于时间扩展的网络K-最短路径算法,满足网络传输一致性假设的前提下,求解大规模定量传输问题。最后给出面向任务的物流保障网络调度的应用实例,获得满意的网络调度优化方案。     

时延受限组播路由的最短路径加速算法求解

分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。     

基于交通网络最短路径搜索的改进算法

对全源最短路径搜索算法进行了深入的研究分析,并结合国内城市道路交通的实际情况,提出了基于边序列最短路径搜索算法的一种改进算法——EBSP*算法。该算法在平均时间复杂度上比传统的Floyd最短路径搜索算法有较大的提高。     

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.     

A comparison of algorithms for origin–destination matrix generation on real road networks and an approximation approach

This paper considers the generation of the origin–destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some nodes. Candidate methods for this are repetitive use of one-to-all shortest path algorithms such as Dijkstra’s algorithm, use of all-to-all shortest path algorithms such as the Floyd–Warshall algorithm, and use of specifically designed some-to-some shortest path algorithms. This paper compares the performance of several shortest path algorithms in computing OD matrices on real road networks. Dijkstra’s algorithm with approximate bucket data structure performed the best for most of the networks tested. This paper also proposes a grouping-based algorithm for OD matrix generation. Although it is an approximation approach, it has several good characteristics: it can find the exact shortest distances for most OD pairs; it guarantees that all the calculated shortest path distance values have corresponding paths; the deviation of any distance from the corresponding true shortest distance is small; and its computation time is short.     

基于多个QoS约束的路径选择算法

寻找同时满足多个独立的QoS 约束的路径是一个NP 完全问题。提出一种解决多约束路径问题的有效算法———多约束最小跳路径算法( MHMCA) , 该算法首先利用Bellman-Ford 最短路径算法进行标记, 并删除图中的无用链路, 在简化后的图中使用基于堆栈的深度优先搜索算法寻找所有满足约束的最小跳可行路径。最坏情况下, 算法的时间复杂度为O( n3) 。仿真结果表明, 该算法寻找具有最小跳可行路径的成功率高, 接近于最优算法。     

两种最短路径算法的比较

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

不可达顶点剪枝算法及其在最短路径中的应用

[k]步可达性查询用于回答图[G]中从顶点[u]到达顶点[v]最多[k]步是否存在路径,但其多用于无权图的可达性研究。针对加权图,在图中构建了最早到达、逆向最早到达和最晚到达等三个索引,并应用这三个索引实现对不可达顶点的快速剪枝,从而有效地缩减了加权图的规模。运用该方法建立索引并剪枝顶点的时间复杂度与空间复杂度分别为[O(n+e)]和[O(n)],这里[n]和[e]分别为图中顶点的数目和边的数目。该方法可以与Dijkstra算法、Floyd算法和A*算法等多种传统算法相结合,并应用于最短路径求解,从而提高传统算法计算性能。最后以物流配送网络为例进行了实验验证,实验结果表明提出的方法可以正确并高效地对不必要计算的顶点进行剪枝,从而加快了最短路径求解速度,验证了提出方法的有效性。     

最短路算法在生产最优化中的应用

给出了一种基于Djikstra最短路算法的实现，该算法实现可以求得有限权图中任一点到其他所有点的最短路径及相应的距离，并清晰完整地表现求解过程及所得结果。生产领域中的一些多阶段优化决策问题可以转化为最短路径问题，由所给出的算法实现来解决这些多阶段优化问题，可以一次求得各不同阶段内的最优策略。以求解设备更新问题和原料选用问题为例，显示了这一算法实现可以完全而简捷地解决多阶段优化决策问题的特点，是最短路算法在生产过程最优化领域的有效运用。     

基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.