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

摘要：

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法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