一种基于移动IPv6路由寻址的最短路径优化算法

移动IPv6的路由寻址是一个最短路径优化问题,最著名的两种最短路径算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,这两种算法的时间复杂度都是O(n3).本文通过对这两种经典算法的研究与分析,提出一种求最短路径的优化算法.该算法的时间复杂度是O(e*n),在连通图中,该算法能够比Floyd算法少近50%的迭代次数,在非连通图中e<相似文献   

Floyd最短路径算法的动态优化

根据Floyd最短路径算法的三层循环,设计了动态优化新算法。动态优化新算法设计了独特的动态AV集合、可发表B和可达表A,分别对原算法的外层循环、中层循环和内层循环进行极小化的运算。在极小化的处理过程中,为保证可发表B和可达表A中不存在重复元素,引入了仅一次插入矩阵M。动态优化新算法的时间复杂度为O(n2+｜AV｜×e2/n2)(｜AV｜!n),使得算法能够根据点数、边数和边的实际分布动态调整自身的性能。     

Dijkstra算法在停车诱导系统中的应用

路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径.传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O（n2）,存在搜索速度慢和浪费空间的缺点.为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O（nlog2n）.用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径.     

对Dijkstra算法的优化策略研究

Dijkstra算法是许多工程解决最短路径问题的理论基础,但实际工程中涉及到的许多限制条件要求人们必须对该算法进行改进和优化。文中在对经典的Dijkstra算法思想进行分析的基础上,论述了Dijkstra算法的一种改进算法———A*算法,并对它们之间的联系进行了剖析。在总结了一个实际工程项目开发的基础上,提出了一种基于Dijkstra算法上的针对铁路中两站点最优路径算法。文中提出的算法通过提取出铁路中的关键站点组成一个新图,之后将起点和终点插入到新图中,经过最多四次的排列组合后选出一个最短路径;该优化方法能将Dijkstra算法的时间复杂度o(n2)中的n降到一个很小的值。实践证明该方法在实际工程中完全可行且已取得了令人满意的效果。     

基于GIS系统的动态最短路径的研究与应用

文章通过对经典Dijkstra算法的研究,提出了从起点到终点所用时间最短的路径的方法。即所谓的时间最短路径算法,确定了改进Dijkstra算法对路段动态阻抗的获得方法。     

对Dijkstra算法的优化策略研究

Dijkstra算法是许多工程解决最短路径问题的理论基础，但实际工程中涉及到的许多限制条件要求人们必须对该算法进行改进和优化。文中在对经典的Dijkstra算法思想进行分析的基础上，论述了Dijkstra算法的一种改进算法——A＊算法，并对它们之间的联系进行了剖析。在总结了一个实际工程项目开发的基础上，提出了一种基于Dijkstra算法上的针对铁路中两站点最优路径算法。文中提出的算法通过提取出铁路中的关键站点组成一个新图，之后将起点和终点插入到新图中，经过最多四次的排列组合后选出一个最短路径；该优化方法能将Dijkstra算法的时间复杂度o（n^2）中的n降到一个很小的值。实践证明该方法在实际工程中完全可行且已取得了令人满意的效果。     

遗传算法和Dijkstra算法在动态权值系统中的比较

针对遗传算法和Dijkstra算法在求解动态权值系统中最短路径时的性能问题,采用比较法,将两种算法应用在同一个实际游戏模型中,对其算法的稳定性、智能性、时间复杂度进行对比测试。游戏模型模拟了各种条件下的动态权值系统。为了使遗传算法更加可靠,通过优化其变异过程使得收敛速度更快,可靠性更高。实验数据表明,遗传算法在每张地图上的得分数以及算法所用时间普遍高于Dijkstra算法,从而得出遗传算法在求解动态权值系统中最短路径问题时稳定性和预期效果明显好于Dijkstra算法,但其时间复杂度较高的结论。     

基于背离路径的Kth最短路径实用搜索算法

基于背离路径的概念,设计Kth最短路径实用搜索算法.通过对第K-1最短路径求背离路径,求得第K最短路径.算法时间复杂度限制在O(e×n2),其中e为图的总边数,n为图的顶点数.在实时应用中,文中的算法有很好的应用前景.该算法已经成功应用到一个传输网络规划系统的动态RWA问题中.     

适用于无向网络的动态Dijkstra算法优化

网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算。动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究。在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法。算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化。为了验证算法的正确性,用仿真实验实现了该算法并与静态算法进行性能比较。实验结果表明,新算法更能提高节点更新的时间效率。     

Dijkstra最短路径算法分析与改进

Dijkstra算法是计算最短路径的经典算法,在对该算法分析的基础上,对其进行了优化和改进。其一是对数据存储方式进行了改进,其二是对辅助向量采用堆排序改进。通过优化降低了内存消耗,搜索效率明显提高。     

GIS中最短路径的求取及三维可视化

最短路径是GIS网络分析的主要问题之一,而经典的Dijkstra算法是目前解决这一问题的理论基础。论文在Dijkstra算法的基础上,根据Shape矢量地图的自身特点,对算法的存储结构和算法过程进行了相应的设计,完成了最短路径的显示。并且最终分别利用一种求交和插值算法,结合OpenGL实现了最短路径在三维地形(基于规则格网)中的可视化,从而为用户提供了一个更加真实沉浸的可视化环境。     

基于遗传算法的动态网络中最短路径问题算法

提出了一种以随机Dijkstra最短路径算法为基础,运用遗传算法来求解动态路径诱导系统 中最短路径问题(ShortestPathproblemonDynamicRouteGuidanceSystem,SPDRGS)的算法。通过运用 该随机Dijkstra算法解决了将遗传算法应用与最短路径问题中初始种群的产生问题。考虑到目前动态 路径诱导系统(DynamicRouteGuidanceSystem,DRGS)对路径诱导算法的时间复杂度和网络约束条件 的要求,此算法不仅能够较快地求出较优的路径而且对网络没有任何的约束条件,同时对离散和连续的 动态网络模型有效,因此符合DRGS的要求。     

一种端到端网络的不相交多路径QoS路由算法

不相交多路径路由算法旨在一个端到端的网络中为应用流选择多个路径，且这些路径在瓶颈链路上是彼此不相交的。本文提出的不相交多路径QoS路由（DMQR）算法在Dijkstra最短路径和最短最宽路径（SWP）算法的基础上，能够动态地计算时延最短、带宽最宽、在瓶颈链路上互不相交的路径，且保证每个路径都是满足一定服务质量的。在视频会议、远程医疗和远程教育等重要的视频通信场合，要求应用层和网络层必须协同工作以保证一些必要的QoS，例如端到端的带宽、时延和包丢失率等。本文针对端到端的网络，重点讨论不相交多路径QoS路由算法在应用层的设计和实现。性能分析和模拟结果显示，所提出的不相交多路径QoS路由算法总是收敛的，且当网络流量增加时，该算法具有较低的包丢失率和较高的吞吐量。     

An advanced GA–VNS combination for multicriteria route planning in public transit networks

Nowadays, passengers in urban public transport systems do not only seek a short-time travel, but they also ask for optimizing other criteria such as cost and effort. Therefore, an efficient routing system should incorporate a multiobjective analysis into its search process. Several algorithms have been proposed to optimally compute the set of nondominated journeys while going from one place to another such as the generalization of the algorithm of Dijkstra. However, such approaches become less performant or even inapplicable when the size of the network becomes very large or when the number of criteria considered is very important. Therefore, we propose in this paper an advanced heuristic approach whereby a Genetic Algorithm (GA) is combined with a Variable Neighborhood Search (VNS) to solve the Multicriteria Shortest Path Problem (MSPP) in multimodal networks. As transportation modes, we focus on railway, bus, tram and pedestrian. As optimization criteria, we consider travel time, monetary cost, number of transfers and the total walking time. The proposed approach is compared with the exact algorithm of Dijkstra, as well as, with a standard GA and a pure VNS. Experimental results have been assessed by solving real life itinerary problems defined on the transport network of the city of Paris and its suburbs. Results indicate that the proposed combination GA–VNS represents the best approach in terms of computational time and solutions quality for a real world routing system.     

低代价最短路径树的快速算法

低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.     

海量道路数据下的最短路径规划效率

通过内存映射完成大拓扑文件的快速加载,估价函数快速过滤无效点和路段,折线简化算法加速长路径的显示等手段,解决了海量道路数据下的最短路径规划效率问题。经比较分析与实践检验证明,规划算法的综合性能指标小于5秒,具有较好的工程应用价值。     

一种满足时延和时延差约束的组播路由算法

针对时延和时延差约束的组播路由优化问题,提出一种最优代价组播路由算法。基于Dijkstra最短路径树算法,通过指示函数调整新加入节点的优先级,利用局部信息构建低代价组播树,使其能较好地平衡组播树代价、时延和时延差之间的关系。仿真实验结果表明,该算法能正确构造出满足时延和时延差约束的组播树,同时具有时间复杂度低、求解成功率高等综合性能。     

基于改进Dijkstra算法的配用电通信网流量调度策略

针对配用电通信网中数据汇聚易产生拥塞的问题,提出了一种复合边权值流量调度路由算法。首先,依据跳数建立节点分层模型;然后,划分配用电业务优先级和节点拥塞等级;最后,以跳数、流量负载率和链路利用率为综合指标计算边权值,对需要流量调度的节点根据改进的Dijkstra算法进行路由选择,同时对重度拥塞节点按照配用电业务优先级进行调度。与最短路径（SPF）算法和贪婪背压算法（GBRA）相比,在数据生成率为80 kb/s时,所提算法紧急型业务丢包率分别减少了81.3%和67.7%,关键型业务丢包率分别减少了79%和63.8%。仿真结果表明,所提算法能有效缓解网络拥塞,提高网络有效吞吐量,降低网络端到端时延和高优先级业务的丢包率。     

基于SPB树的公路网络最短路径查询

针对在线地图服务和路程安排等领域中的点对点最短路径查询方法,提出一种新的数据结构——最短路径B+树(SPB树),以有效存储预先计算好的点空间信息和与之对应的最短路径信息.实验结果证明,利用SPB树在公路网络上进行最短路径查询比经典的Dijkstra算法最高快出3个数量级.     

TSP Heuristics: Domination Analysis and Complexity

We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph Kn produce a solution no worse than the average cost of a tour in Kn in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon, Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than $\lceil{n}/{2}\rceil !$ , and for the Double Tree heuristic and a variation of the Christofides heuristic the domination numbers are shown to be one (even if the edge costs satisfy the triangle inequality). Further, unless P = NP, no polynomial time approximation algorithm exists for the TSP on the complete digraph $\vec{K}_n$ with domination number at least (n-1)!-k for any constant k or with domination number at least (n-1)! - (( k /(k+1))(n+r))!-1 for any non-negative constants r and k such that (n+r) $\equiv$ 0 mod (k+1). The complexities of finding the median value of costs of all the tours in $\vec{K}_n$ and of similar problems are also studied.