摘要
Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortestpathtree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-costshortestpathtreealgorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.
Dijkstra algorithm is an excellent shortest path algorithm,which can compute a shortest path between two given nodes and also gain a shortest path tree（SPT） from a source to some destination nodes.It has been widely applied in many aspects of network computing.In order to optimize the cost performance of SPT,a path nodes-driven idea is introduced which derives from the destination nodes-driven idea.By using the idea,an algorithm called least-cost shortest path tree（LCSPT） is designed.To describe LCSPT algorithm in detail,its main running steps and the pseudo codes are introduced.Through LCSPT algorithm,a computing node can share links with path nodes which have belonged to the existing shortest path tree,and so a high-performance least-cost SPT can be constructed.As an important component of LCSPT,its correctness is proofed by mathematical induction,and the cost performance of LCSPT is analyzed in theories.Moreover,the time complex and the space complex are computed and compared with the other SPT algorithms.At last,three simulation experiments are done and the resulted data show that LCSPT algorithm not only produces a SPT tree correctly but also has the best cost performance among all the shortest path tree algorithms.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2011年第5期721-728,共8页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61073036)
国家“九七三”重点基础研究发展计划前期研究专项基金项目(2008CB317107)
广东省自然科学基金项目(10152800001000016)
中南大学博士后基金项目
关键词
SPT算法
最小代价
组播
路径节点驱动
算法分析
仿真
SPT algorithm
least-cost
multicast
path nodes-driven
algorithm analysis
simulation
