低代价最短路径树快速算法的时间复杂度研究

被引：4

作者：

汪维清 ^{[1
]}

汪维华 ^{[2
]}

张明义 ^{[1
]}

机构：

[1] 西南大学计算机与信息科学学院

[2] 重庆文理学院数学与计算机科学系

来源：

计算机工程与设计 | 2007年 / 22期

关键词：

多播; 最短路径树; Steiner树; 最小生成树; 迪克斯曲拉算法; Fibonacci堆;

D O I：

10.16208/j.issn1000-7024.2007.22.026

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗。快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n+e)。FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的。通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!)+e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n)+e)更能体现FLSPT算法高效率。

引用

页码：5468 / 5471

页数：4