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

• 作者: 张明义 汪维华 汪维清
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 多播 最短路径树 Steiner树 最小生成树 迪克斯曲拉算法 Fibonacci堆
• 年，卷（期）: 2007,（22）
• 所属期刊栏目: 人工智能
• 页码范围: 5468-5471
• 页数: 4页
• 分类号: TP301
• 字数: 3805字
• 语种: 中文
• DOI: 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算法高效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪维华	重庆文理学院数学与计算机科学系	31	136	8.0	9.0
2	汪维清	西南大学计算机与信息科学学院	24	83	6.0	7.0
6	张明义	西南大学计算机与信息科学学院	5	21	3.0	4.0