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

Computation complexity research of fast low-cost shortest path tree algorithm

作　　者：汪维清[1] 汪维华[2] 张明义[1] 

机构地区：[1]西南大学计算机与信息科学学院 [2]重庆文理学院数学与计算机科学系,重庆402160

出　　处：《计算机工程与设计》2007年第22期5468-5471,共4页Computer Engineering and Design

基　　金：重庆文理学院重点科研基金项目(Z2006SJ32)

摘　　要：低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗。快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n+e)。FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的。通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!)+e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n)+e)更能体现FLSPT算法高效率。Low-cost shortest path tree is a commonly-used multicast tree type, which can minimize the end-to-end delay and at the same time reduce the bandwidth requirement if possible. Based on the low-cost shortest path tree algorithm DDSP （destination-driven shortest path） and through improving on the search procedure, a fast low-cost shortest path tree （FLSPT） algorithm is presented. The shortest path tree constructed by the FLSPT algorithm is the same as that constructed by the DDSP algorithm, but its computation complexity is lower than that of the DDSP algorithm. It＇s computation complexity is O （nlog n＋e）. The FLSPT is to make use of a Fibonacci heap to choose the minimum value of not-computed nodes to compute its computation complexity. Through the program of the FLSPT and the analyzing of the F ibonacci heap, we found that it is more effective if the computation complexity is O （log （n!） ＋e） and not O （nlog （n） ＋e）.

关 键 词：多播 最短路径树 STEINER树 最小生成树 迪克斯曲拉算法 Fibonacci堆 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]