路径节点驱动的低代价最短路径树算法

被引：20

作者：

周灵 ^{[1
,2
]}

王建新 ^{[2
]}

机构：

[1] 中南大学信息科学与工程学院

[2] 佛山科学技术学院计算机系

来源：

计算机研究与发展 | 2011年 / 48卷 / 05期

基金：

广东省自然科学基金;

关键词：

SPT算法; 最小代价; 组播; 路径节点驱动; 算法分析; 仿真;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortestpathtree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-costshortestpathtreealgorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.

引用

页码：721 / 728

页数：8

共 4 条

[1]

Finding a path subject to many additive QoS constraints [J].