一个求解次短和渐次短路径的实用算法

求解第 k 短路径问题在决策支持系统和咨询系统中具有广泛的用途,本文基于 Dijkstra 算法,给出了一个求解次短路径和渐次短路径的算法,并且分析了算法的时间复杂度和空间复杂度。

基于改进K次短路径算法的有效路径搜索算法及实现

为提高有效路径搜索效率,结合ArcGIS具有的路径分析功能,以K次短路径算法为基础,依据重叠惩罚算法的原理,提出基于改进K次短路径算法的有效路径搜索算法。以ArcGIS为平台,给出了算法的实现方法。经过对实际路网的可视化测试,验证了改进算法具有较高的运行效率,为有效路径相关理论在ArcGIS平台的应用提供了一种技术手段和方法。

基于铁路运输网络的最短路径及次短路径研究

在铁路运输网络中,经常要计算最短路问题,Dijkstra算法和Floyd算法是求最短路径的最常用最有效的两种方法。首先从不同方面对Dijkstra算法和Floyd算法进行了比较分析,然后对次短路问题做了简要介绍。

关于k次短路径问题的分析与求解

分析了前k条最短路径的图论理论基础,在计算出最短路径的基础上,提出了一种基于前k-1条最短路径的k次短路径的求解方法,该方法能方便高效地找出次短路、再次短路,一直到k次短路。该算法的时间复杂度为O(n2),可以很好地满足实际应用需要。

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

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

基于矩阵运算K短路径算法

最短路问题是复杂网络中的经典问题,其求解算法层出不穷,各有优缺点。经典的算法包括Dijkstra算法、Ford算法和Floyd算法等,只能求解两节点间的一条最短路径。在实际生活中,还需要在大型网络中限定一些前提条件求解两点间次短、渐次短的路径问题。为此,提出了一种对距离矩阵和路径矩阵的迭代、替换算法,即从一个节点出发寻找其后继节点,同时通过比较路径长短得到两点间最短路径、次短路径和渐次短路径,并不断重复、替换。为验证所提算法的有效性,以一个大型网络的应用作为实例,应用Matlab对所提算法进行了仿真实验验证。仿真结果表明,所提算法能够在复杂大规模随机网络中满足求解指定顶点间最短、次短和渐次短路径的需要,具有较好的有效性和适用性。

基于最短路径的网络可靠性评估算法

介绍了通信网络可靠性算法的研究现状,分析了各种可靠性算法的优点和不足。从网络拓扑结构和可靠性定义出发,研究了网络可靠性影响因素,建立了可靠性评估模型,对算法思想进行了描述。在网络最短路径和次短路径的基础上,提出了端到端的网络可靠性评估算法,根据网络中的薄弱节点,求得了整个网络可靠性值的近似值。以实例模拟计算,说明其算法的计算过程,验证了算法的准确性。

基于改进A*算法的AGV路径规划

自动引导小车(Automatic Guided Vehicles,AGV)广泛应用于物流自动化系统,针对AGV的路径规划问题,提出了一种改进的A*算法,该算法引入转弯因素,使规划的AGV路径更加平滑;并充分利用求解的最短路径信息,采用一种删除边的算法来求解k次短路径问题;实例仿真证明了改进的A*算法的可行性,通过与其他求解k次短路径问题的算法进行对比,证明删除边的算法简单、可行。

一种基于Dijkstra的实用多路径求解算法

针对传统的多路径求解算法求解的始终是起点到终点的最短路径,搜索区域上一直没有什么变化,效率较低的问题,提出了一种基于Dijkstra的实用多路径搜索算法,只需求解起点到原最短路径上中间节点的最短路径,最后再补充相关路段,便可以得到权值与最短路径相接近的前几条次短路径。最后结合郑州市某区域的交通网络图进行了实例仿真,结果表明该算法是行之有效的。

Kth最短路径的Bellman改进算法

基于对Bellm an算法的改进,得到了求解k th最短路的新算法.改进算法的优势在于从Bellm an算法只能解决最短路问题拓展到求解k th最短路问题,而且可以考虑权重为负数的情况.与传统算法相比,新算法更易于理解.

轨道交通系统票务清分算法

提出了一个实现轨道交通系统票务清分的算法。给出了清分的精确算法 ,在论证精确算法的不可实现性的基础上 ,演变出切实可行的票务清分的近似算法 。

基于Kruskal和Floyd算法的馈线新增负荷接入方法

规划人员一般采用简单的方法对配电网网架进行扩展,以应对配电网有新增负荷节点出现的情况,这可能导致电压质量达不到要求或配电网运行不经济等问题。提出一种基于Kruskal和Floyd算法配电网新增负荷的接入方法,该方法计及了新增负荷前配电系统的无功配置情况。通过Kruskal算法得到配电网网架初始结构,以满足供电半径为目标,运用Floyd算法得到新增负荷接入线路的次短路径,当电压不满足要求时,采用无功二次精确矩法确定无功补偿点的位置和补偿容量,以保证系统的电压质量,并进一步降低线损。对算例进行数字仿真,仿真结果验证了该方法的可行性和实用性。