共查询到18条相似文献,搜索用时 156 毫秒
1.
2.
在通信网络中,节点间最短路径的计算是链路状态路由协议计算路由的基础。通过对现有动态最短路径算法的深入研究,提出了一种处理网络拓扑变化的完全动态最短路径算法DSPT-ID。该算法利用已有SPT的信息,建立一个最短路径树的更新队列,当网络拓扑发生变化时,算法针对边的权值增大和减小,分别进行更新,并将更新节点局限在受拓扑变化影响的节点中,从而达到SPT的增量更新。算法复杂度分析和仿真结果显示,DSPT-ID算法具有更少的节点更新次数和更高的时间效率。 相似文献
3.
4.
5.
网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算。动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究。在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法。算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化。为了验证算法的正确性,用仿真实验实现了该算法并与静态算法进行性能比较。实验结果表明,新算法更能提高节点更新的时间效率。 相似文献
6.
7.
网络最短路径的动态算法 总被引:3,自引:1,他引:3
在通信网络中,两个节点间最短路径的计算是大多数路由算法的基础,对整个网络的性能有重要的影响。该文针对动态变化的网络环境,提出了一种快速的动态最短路径树算法(DMDT),并给出了算法的实现步骤。随机网络模型的仿真结果表明:DMDT算法生成的最短路径树与Dijstra算法基本一致,计算的时间复杂度较Dijstra算法有很大降低。为动态最短路径树的计算提供了一种新的选择。 相似文献
8.
低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高. 相似文献
9.
多播路由KPP算法的改进 总被引:1,自引:1,他引:0
论文提出一种满足端到端时延限制的多播路由算法。该算法参考KPP[7]算法,在构造多播路由树的过程中动态调整路径的选取,使尽可能地共享网络中的链路,并对所构造的多播树进行进一步的调整优化,最后得到一棵低代价的满足端到端时延限制的多播路由树。论文通过对KPP算法进行分析发现KPP算法思想忽略了对转发节点的处理,而且在两节点间路径的选取过程中仅仅选取最佳路径,这就导致了对边稠密的图,KPP算法存在缺陷。算法基于上述缺陷完善了KPP算法,在复杂的网络图中应用该算法比KPP算法更加有效,实验模拟表明该算法构造的多播树与KPP算法构造的多播树相比能优化9%到10%。 相似文献
10.
11.
Dynamic algorithms for the shortest path routing problem: learning automata-based solutions. 总被引:2,自引:0,他引:2
Sudip Misra B John Oommen 《IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics》2005,35(6):1179-1192
This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking. 相似文献
12.
基于共享边的时延约束组播路由算法 总被引:3,自引:2,他引:1
为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH.该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价.仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能较好. 相似文献
13.
14.
在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t). 相似文献
15.
一种计算因特网AS拓扑的最短路径的快速算法 总被引:2,自引:1,他引:1
最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间. 相似文献
16.
周培德 《计算机工程与科学》2002,24(4):35-37
寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。 相似文献
17.
Cees Duin 《Algorithmica》2005,41(2):131-145
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. 相似文献
18.
Cees Duin 《Algorithmica》2004,41(2):131-145
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. 相似文献