10.3969/j.issn.1000-7024.2007.22.044
低代价最短路径树快速算法的时间复杂度研究
低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n+e).FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的.通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!)+e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n)+e)更能体现FLSPT算法高效率.
多播、最短路径树、Steiner树、最小生成树、迪克斯曲拉算法、Fibonacci堆
28
TP301(计算技术、计算机技术)
重庆文理学院重点科研基金Z2006SJ32
2008-05-21(万方平台首次上网日期,不代表论文的发表时间)
共4页
5468-5471