低代价最短路径树的快速算法

被引：29

作者：

王涛

李伟生

机构：

[1] 北京交通大学计算机与信息技术学院

来源：

软件学报 | 2004年 / 05期

关键词：

多播; 最短路径树; Steiner树; 最小生成树;

D O I：

10.13328/j.cnki.jos.2004.05.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast low-cost shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.

引用

页码：660 / 665

页数：6