一种基于最小树的组播路由算法  

A Sort of Multicast Algorithm on the Basis of Minimum Tree

作　　者：岳远振[1] 韩海山[2] 

机构地区：[1]大连理工大学应用数学系,辽宁大连116024 [2]内蒙古民族大学数学与计算机科学学院,内蒙古通辽028043

出　　处：《内蒙古民族大学学报（自然科学版）》2005年第2期130-132,共3页Journal of Inner Mongolia Minzu University：Natural Sciences

基　　金：国家教委博士点专项基金(20020141013)

摘　　要：文章研究了最小树的一些特点,推广了Dijkstra算法,并在此基础上提出了一个适用于网上电影在线收看系统的组播路由算法.在求组播树的过程中,首先利用Prim算法求出包含给定节点集的最小树,再根据最小树的特点,利用推广的Dijkstra算法为最小树中不满足约束条件的节点重新寻路,直到树中所有的节点都满足约束条件.In this paper,some properties of minimum tree is investigated and the Dijkstra algorithm is generalized.On the basis of this,a sort of multicast algorithm is applied to on-line video on the internet.In the process of finding multicast tree,the minimum tree comprising the given nodes is found firstly with the Prim algorithm,then,the multicast algorithm looks for routings again for the nodes which violate the constraints with the generalized Dijkstra algorithm according to the properties of minimum tree.The algorithm terminates till there is no node in the tree violates the constraints.

关 键 词：运筹学 组播路由算法 最小树 PRIM算法 推广的Dijkstra算法 

分 类 号：O221.4[理学—运筹学与控制论]