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

作者：汪维清; 汪维华; 张明义

来源：计算机工程与设计, 2007, (22): 5468-5471.

• 多播
• 最短路径树
• Steiner树
• 最小生成树
• 迪克斯曲拉算法
• Fibonacci堆 multicast
• shortest path tree(SPT)
• Steiner tree
• minimum spanning tree(MST)
• Dijkstra algorithm
• Fibonacci heap

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

• 单位
  重庆文理学院; 西南大学; 西南大学荣昌校区