多播是目前网络中研究最多、应用最广的通信方式.实现多播路由是解决多播通信的关键问题之一,而实现多播路由的一般方式是建立多播树.多播路由算法主要用来建立一棵性能好的多播树,并使它满足各种业务的服务质量(Quality ofService,简记为QoS)需求.最短路径树(Shortest Path Tree,简记为SPT)是应用最多的多播树类型之一.在大型网络中,两节点间的最短路径可能有多条,因而导致相应的最短路径树不唯一,不同最短路径树的总代价也不尽相同.该文主要研究如何降低最短路径树的总代价,在确保传送时延最小的同时尽量降低带宽消耗.该文的主要研究工作如下:1.该文总结了最短路径树的各种启发式算法,分析了各种算法的的复杂度、适用情况和特点,这为后面的工作打下了基础.2.对已有的一些最短路径树静态算法进行深入分析,指出其不足之处,并在此基础上给出一种改进算法,通过改进搜索过程,使得在多播树性能保持不变的情况下时间复杂度更低.3.对于网络中两节点间所有最短路径的求解问题,提出了一种新的结构——最短路径子图,用来存储两节点间的所有最短路径信息,可以节省存储空间.并给出了最短路径子图的构造算法,其时间复杂度要远低于原有求解两点间所有最短路径的算法.4.研究了已有的一些最短路径树动态算法,指出其效率低下的原因.利用最短路径子图的性质,提出了一种新的动态算法,其计算效率和生成的多播树性能都要优于原有算法.5.对以上算法进行程序实现,验证了算法的正确性,并与一些典型算法进行比较,取得了较好的结果.6.最后对多播路由算法今后的研究工作提出了一些设想和看法.