一种任意城市间最短路线优化算法实现

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

基于改进的Floyd算法求节点间所有最短路径

网络节点间的最短路径可能不止一条.首先运用加速的Floyd算法得到最短路径长度矩阵;然后根据最短路径长度矩阵构造各个节点的到达距离矩阵,用来与最短路径长度矩阵进行对比;最后得到每个节点的后继节点,进而得到所有最短路径.计算机仿真验证了该算法的高效性.     

Floyd算法在中心小学选址上的应用

中心小学选址是一个非常重要的问题。是将地理信息作为选址的主要依据,将几个相邻的村子的地理信息抽象成数学当中的图,然后用图论中求中心点和中位点的方法来确定中心小学的位置。在求中心点、中位点时要用到图论中最短路径算法,对经典的最短路径算法Floyd算法作了介绍。最后,用实例来分析中心点与中位点选址模型,并对中位点模型作了进一步分析。     

改进的Floyd算法在套牌车辨别中的应用

针对套牌车辨别中用传统Floyd算法计算最短路径距离存在效率低和速度慢等问题,文中提出了一种改进的Floyd算法,减少了矩阵迭代过程中任意两点之间的最短路径计算量,提高了算法效率。在MATLAB中用同一矩阵对改进前后的Floyd算法进行仿真和比较,结果表明,改进后的算法在效率上高于传统算法。运用某市交通数据集辨别套牌车时,改进的Floyd算法效率比传统Floyd算法的效率提升了近30%,说明了改进的Floyd算法的高效性和实用性。     

基于最短路问题模型的巡航导弹航迹判定

最短路问题是图论中一个多阶段决策问题。首先,通过研究巡航导弹飞行特点,确定其航迹规划属于多阶段决策问题,从而提出运用最短路问题模型判定巡航导弹航迹;其次,提出判定巡航导弹航迹的最短路问题模型的顶点的确定方法,给出了加权系数的概念及权的确定方法;最后,选定某抗击巡航导弹战例,运用最短路模型对巡航导弹航迹进行判定,结果验证了该方法的有效性和可行性。     

中国邮路最短路问题的研究

中国邮路问题意义重大,在现实中应用广泛。中国邮路问题即利用一种计算方法来求解邮递员投递所需要经历的最短路线。该方法把邮递线路看作连通加权无向图,然后通过Fleury算法求解得到最优邮路。在实际例子的求解过程中,发现该方法并不能求出唯一解即存在次优解。我们将继续研究邮路问题以便获得最佳的计算方法。     

软件定义网络中基于时延的Floyd算法

随着网络技术的不断演进,软件定义网络已成为一种解决现有网络问题的技术趋势。在软件定义网络技术集中式控制平面的特点下,利用开放以及开源的软件定义网络技术,文章对其所承载的网络业务进行基于时延的Floyd算法方面的相关研究,提出一种以链路时延数据为权重的Floyd算法,作为软件定义网络控制器选择网络业务时延最优路径的方法;同时建立了Ryu和Mininet软件组成的软件定义网络仿真实验环境,在此环境中进行软件定义网络全局的链路延时原理分析以及测量,并完成了实验环境设计和结果验证,实现了降低网络业务时延的目的。     

求解最短路径问题的改进人工鱼群算法研究

最短路径问题是交通网络分析中的一个重要问题,它是组合优化领域内经典问题之一。文中分析基本人工鱼群算法模型,指出其在求解交通路网最优路径问题中的不足,对人工鱼初始化和行为进行了改进。仿真实验表明,改进的人工鱼群算法(AFSA)具有更快的全局收敛速度,能有效地克服"早熟"收敛,是一种有效解决最短路径问题的寻优模式。     

New dynamic algorithms for shortest path tree computation

The open shortest path first (OSPF) and IS-IS routing protocols widely used in today's Internet compute a shortest path tree (SPT) from each router to other routers in a routing area. Many existing commercial routers recompute an SPT from scratch following changes in the link states of the network. Such recomputation of an entire SPT is inefficient and may consume a considerable amount of CPU time. Moreover, as there may coexist multiple SPTs in a network with a set of given link states, recomputation from scratch causes frequent unnecessary changes in the topology of an existing SPT and may lead to routing instability. We present new dynamic SPT algorithms that make use of the structure of the previously computed SPT. Besides efficiency, our algorithm design objective is to achieve routing stability by making minimum changes to the topology of an existing SPT (while maintaining shortest path property) when some link states in the network have changed. We establish an algorithmic framework that allows us to characterize a variety of dynamic SPT algorithms including dynamic versions of the well-known Dijkstra, Bellman-Ford, D'Esopo-Pape algorithms, and to establish proofs of correctness for these algorithms in a unified way. The theoretical asymptotic complexity of our new dynamic algorithms matches the best known results in the literature     

Asymptotic optimality of shortest path routing algorithms

Many communication networks use adaptive shortest path routing. By this we mean that each network link is periodically assigned a length that depends on its congestion level during the preceding period, and all traffic generated between length updates is routed along a shortest path corresponding to the latest link lengths. We show that in certain situations, typical of networks involving a large number of small users and utilizing virtual circuits, this routing method performs optimally in an asymptotic sense. In other cases, shortest path routing can be far from optimal.     

机器人避障中最短路径的算法研究及应用

基于机器人在平面区域运动的避障问题,通过单一障碍物路径长度设计算法,利用MATLAB软件进行分别计算,综合比较得出机器人从区域起点到达目标点的避障最短路径。     

最短路程的运输问题及解法

针对最短路程的运输问题,建立了模型,研究了其解的最优性充分条件,提出了一种简捷、快速的求解方法,并给出了具体的求解步骤,最后用实例表明了解法的可操作性。     

基于BFS算法的有阻断路径的最短路径算法研究

针对大规模网络中所有节点的全源最短路径的计算需求,文中基于广度优先遍历(BFS)思想,在计算过程中设置存储队列,引入阻断路径,限制后续图节点的扩展范围,完成了图的减枝,大幅度降低最短路径计算的时间复杂。经测试,文中所设计的算法相较于传统Dijkstra算法在高、中、低规模的数据集上均可降低50%以上的运算时间;相较于BFS算法,可以降低20%以上的运算时间。     

On the complexity of and algorithms for finding the shortest path with a disjoint counterpart

Finding a disjoint path pair is an important component in survivable networks. Since the traffic is carried on the active (working) path most of the time, it is useful to find a disjoint path pair such that the length of the shorter path (to be used as the active path) is minimized. In this paper, we first address such a Min-Min problem. We prove that this problem is NP-complete in either single link cost (e.g., dedicated backup bandwidth) or dual link cost (e.g., shared backup bandwidth) networks. In addition, it is NP-hard to obtain a K-approximation to the optimal solution for any K>1. Our proof is extended to another open question regarding the computational complexity of a restricted version of the Min-Sum problem in an undirected network with ordered dual cost links (called the MSOD problem). To solve the Min-Min problem efficiently, we introduce a novel concept called conflicting link set which provides insights into the so-called trap problem, and develop a divide-and-conquer strategy. The result is an effective heuristic for the Min-Min problem called COnflicting Link Exclusion (COLE), which can outperform other approaches in terms of both the optimality and running time. We also apply COLE to the MSOD problem to efficiently provide shared path protection and conduct comprehensive performance evaluation as well as comparison of various schemes for shared path protection. We show that COLE not only processes connection requests much faster than existing integer linear programming (ILP)-based approaches but also achieves a good balance among the active path length, bandwidth efficiency, and recovery time.     

基于PCNN的迷宫最短路径求解算法

本文根据脉冲耦合神经网络(PCNN)并行运行的特点,提出了基于PCNN模型的迷宫最短路径搜索算法。从理论上对该算法进行了分析和讨论,并给出了具体的算法和实验结果,验证了该方法的有效性。与其他算法相比,该方法可以在最短的时间内完成最短路径的搜索。