一种高效的最短路径完全动态更新算法

在通信网络中,节点间最短路径的计算是链路状态路由协议计算路由的基础。通过对现有动态最短路径算法的深入研究,提出了一种处理网络拓扑变化的完全动态最短路径算法DSPT-ID。该算法利用已有SPT的信息,建立一个最短路径树的更新队列,当网络拓扑发生变化时,算法针对边的权值增大和减小,分别进行更新,并将更新节点局限在受拓扑变化影响的节点中,从而达到SPT的增量更新。算法复杂度分析和仿真结果显示,DSPT-ID算法具有更少的节点更新次数和更高的时间效率。     

一种高效的最短路径树动态更新算法

计算动态环境下最短路径树是一个典型的组合优化问题。Ba11-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算。针对Ba11-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。     

动态网络中一种高效的最短路径树维护算法

现有的动态最短路径树算法在某些边的权值频繁变化时,会造成动态网络中的最短路径树频繁更新,而且当网络中的路由器毁坏或增加新的路由器时,该算法难于应用到构造最短路径树中。针对上述问题,提出一种最短路径树的维护算法。对权值频繁变化的边进行处理,避免将其加入到最短路径树中,减少最短路径树的更新次数,当网络中的路由器毁坏或者增加时,通过减少冗余边的入队操作,对网络中的最短路径树进行维护。实验结果表明,与高效的最短路径树动态更新算法相比,该算法的更新时间效率更高。     

动态最短路径算法及其仿真

最短路径算法广泛应用在GIS(地理信息系统)、机器人探路、计算机网络等领域,经过几十年发展,有了很大进展.现在流行的最短路径算法有Dijkstra算法、A*算法,它们都建立在信息完全准确、静态路网的前提下.但现实中信息常常不准确、不完整,路途环境不断变化.当环境变化时,需要重新修改整个路径,因而速度较慢.介绍一种动态最短路径算法,初始时建立好最短路径,当环境变化时,可以只计算变化处附近局部节点,减少计算量,从而较迅速做出新的最短路径选择.最后经过仿真看出,路网中节点越多,动态最短路径算法优势越大.     

基于路由最短路径树的动态多节点删除算法

提出一种基于路由最短路径树的多节点删除动态算法。算法建立一个最短路径树更新队列,将所有将被删除节点的子孙节点保存到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,已更新节点不再被插入队列,从而减少节点更新次数。实验结果表明,该算法能有效减少节点的更新冗余。     

最短路径算法及其实现

本文主要讨论了两种典型的最短路径算法-Dijkstra算法和Ford-Fulkerson算法的设计思路,并给出了其实现过程。     

最短路径树的计算与修改算法

在有向赋权图Ｇ＝（Ｖ，Ｅ，ＣＯＳＴ）上，给出了求解以每个顶点为根的向前／向后最短路径树（ＦＢＳＰＴ）算法。当Ｇ中的边被删除或边权增加时，证明了在这种情况下，不可能存在高效的对ＦＢＳＰＴ的修改算法；而对边添加和边权减少的情况，本文给出时间复杂性为Ｏ（ｎ￣２）的修改算法。此外，本文也讨论了对上述算法的并行实现问题。     

单源点最短路径动态优化算法

设计了最短路径时间复杂度取决于边数e和点数n的动态优化算法。采用了独特的动态PV集合链,改进了当前求得的最短路径向量D的存储结构,用PV集合链对向量D进行动态管理,使其时间开销为e+(n-1)×(n-2)/2+3n。当n>4时,SPD OA算法的性能明显优于Dijkstra算法,呈现出良好的动态优化特性。最后对动态优化算法与Dijkstra算法用理论公式得出的数据进行了时间性能比较。     

最短路径重构算法

研究了在Ｎ个顶点的图中，仅给出了所有顶点对之间最短路径距离矩阵，而计算任两顶点间最短路径问题。这种算法因没有利用原始图中有关边的信息，被称为重构算法。本研究取得了如下成果：①在单一的顶点对之间最短路径重构的时间复杂度为Ｏ（ｎｌｏｇｎ）；②在所有顶点对之间的最短路径重构的时间复杂度为Ｏ（ｎ＾３）；③在带有ｎ／ｌｏｇｎ个处理器的独占读写并行随机访问器上，单一顶点对之间的最短路径重构时间复杂度为Ｏ（（ｌ     

一种基于离散变权网络的动态最短路径快速算法

在离散变权动态网络中,求解最短路径的最优化算法的计算复杂性通常远大于O(n2),不适用于实时的动态交通信息导航系统。提出的动态最短路径快速算法,是在所有的当前点与下一个待选点之间以及待选点与目标点之间的动态弧的权值之和中选择一个最小值,然后把该待选点作为当前点继续选择下一个待选点,如此反复,直到达到目标点为止。该算法所得到的路径是一个次优解,但其执行时间却比寻找最优解算法要小得多,并且所得到的解要优于选择最短距离路径的动态解。实验结果证明这是一种适用于动态交通导航的有效算法。     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

一种新的Kth最短路径搜索算法

借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。     

基于二度量的单播最短路径算法

随着网络应用的日趋复杂,多度量的网络描述也在增多。针对网络的二度量单播最短路径问题,结合适当的路径长度判定函数,该文提出了一种能保持路径计算过程中的真实状态的新算法,不必预先进行处理,计算过程中通过判定函数来减少搜索空间,从而减少计算量,具有良好的可扩展性,可扩展到多度量模式。     

求解区间图K-连接最短路径问题的在线算法

针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。     

煤矿紧急救援实时最短路径的研究

煤矿事故紧急救援是一个艰难的任务,救援的关键是探明事故的发生地点、事故的影响范围和救援的最短路径.论文采用GIS独特的空间分析功能,构造了煤矿项目的关系模型和巷道数据库,建立了基于Dijsktra优化算法的实时最短路径搜索算法,为紧急救援指明了最短救援路径,给出了分析过程和可行性证明.     

基于改进伊藤算法的最短路径网络路由优化算法

通过对网络路由最短路径问题进行分析,使用伊藤算法求解以费用最低为目标的路由优化问题,建立最短路径路由问题的网络结构模型。为加快伊藤算法求解费用最低路由的收敛速度,在状态转移策略中引入费用启发因子,优化漂移和波动过程,并改进路径权重更新规则。将种群交叉思想引入算法中,利用种群间的信息交流加快了算法的收敛速度并提高了寻优能力。在2-opt算子局部优化的基础上加入反转算子,避免陷入局部最优解。文中还对算法的收敛性进行了系统分析。实验结果表明,改进后的算法有效提升了收敛速度并加强了寻优能力。