| 路径节点驱动的低代价最短路径树算法 |
| |
| 引用本文： | 周灵,王建新.路径节点驱动的低代价最短路径树算法[J].计算机研究与发展,2011,48(5). |
| |
| 作者姓名： | 周灵 王建新 |
| |
| 作者单位： | 1. 中南大学信息科学与工程学院,长沙,410083;佛山科学技术学院计算机系,广东佛山,528000
2. 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金项目，国家"九七三"重点基础研究发展计划前期研究专项基金项目，广东省自然科学基金项目，中南大学博士后基金项目 |
| |
| 摘 要： | Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.
|
| 关 键 词： | SPT算法 最小代价 组播 路径节点驱动 算法分析 仿真 |
Path Nodes-Driven Least-Cost Shortest Path Tree Algorithm |
| |
| Zhou Ling,Wang Jianxin.Path Nodes-Driven Least-Cost Shortest Path Tree Algorithm[J].Journal of Computer Research and Development,2011,48(5). |
| |
| Authors: | Zhou Ling Wang Jianxin |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
