多播是一种群组通信的手段，要求将信息从一个数据源同时传送到多个目的地。构造多播树是解决多播路由问题的常用方法。有3种不同类型的多播树：基于数据源的树、Steiner树和基于中心的树。这些不同类型的树中具有代表性的是基于源的最短路径树(shortest path tree，简称SPT)和Steiner树。SPT最主要的优点就是它使得源结点到每个目的结点的时延最小：而Steiner树则使得所有连接的消耗总和最小，最大限度地共享带宽，如果网络中除源结点外的每个结点都是目的结点，这棵树就是最小生成树(minimum spanning tree，简称MST)。在给定的网络中，构造从源结点到其他目的结点的多播树，几乎不可能使它同时达到最小延时和最小总消耗，因此，一些学者研究构造满足指定时延限制的Steiner树。当网络变得足够大时，从源结点到一些目的结点的最短路径常常不只一条，而由此构成的SPT也就不是惟一的。在众多的SPT中，每棵树的总消耗也不尽相同。因而，有必要研究如何降低SPT的总消耗问题。最优最短路径树算法SBPT(shortest best path tree)，是通过在构造SPT的过程中采用贪心策略选择最短路径，使所构造的生成树的总消耗得以降低。该算法的时间复杂度较高而不适合大型网络求解。驱动多播路由算法DDMC(destination-driven multicasting)，是通过使目的结点之间尽可能共享路径来降低多播树的总消耗。驱动最短路径树算法DDSP(destination-driven shortest path)采用Dijkstra算法路径递增的基本思想，并结合DDMC算法目的结点共享路径的方法，当源结点到某结点的最短路径不惟一时，总是选择一条与其他目的结点的共享路径最长的最短路径，从而降低所构造SPT的总消耗。它因而适合计算目的结点数较多的最短路径树。低代价最短路径树的快速算法FLSPT(fast low-cost shortest path tree)是在DDSP算法的基础上进行改进，它构造的多播树与DDSP算法构造的多播树具有相同性能，但时间复杂度比DDSP算法要低。仔细研究FLSPT算法可以发现，在Q集合中选择了距源点S的路径最小的点u后，如果不把该u点从Q集合中删除掉，就会出现死循环；同时，如果u是目的结点，如果不把该结点从目的结点集合里删除也会出现死循环。因此，必须在算法中加两语句：Delete u from Q和Delete u from D。同时，FLSPT在分析时间复杂度时，没考虑到从待发展结点序列Q中选择并删除结点时，每循环一次就减少一个结点，因此，FLSPT的时间复杂度可以用更优的表达式来表达。实验表明Dijkstra算法中待发展结点的插入具有很强的插入局部性，即结点的插入概率分布不均衡。据此，提出一种基于有序双循环链表的FLSPT算法。仿真实验表明，该算法比FLSPT算法效率可以提高19％。