基于路由最短路径树的动态多节点删除算法  

Dynamic Multi-node Remove Algorithm Based on Routing Shortest Path Tree

作　　者：梁德恒[1] 姚国祥[1] 官全龙[1] 

机构地区：[1]暨南大学信息科学技术学院,广州510632

出　　处：《计算机工程》2011年第5期121-123,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60773083);广东省高校科技成果转化基金资助重大项目(cgzhzd0807);广东省教育部合作专项基金资助项目(2008B090500201);广东省科技计划基金资助项目(2009B010800023)

摘　　要：提出一种基于路由最短路径树的多节点删除动态算法。算法建立一个最短路径树更新队列,将所有将被删除节点的子孙节点保存到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,已更新节点不再被插入队列,从而减少节点更新次数。实验结果表明,该算法能有效减少节点的更新冗余。This paper proposes a multi-node removed dynamic algorithm based on routing Shortest Path Tree（SPT）.The algorithm establishes an SPT update queue to preserve all the descendent nodes of removed nodes;deletes nodes that needed to be removed and their descendent nodes from original SPT;selects a node with the shortest distance to the source node from the queue to carry on the updating.In order to reduce the updated frequency,the node can not be inserted into the queue again after updating.Experimental result shows that this algorithm can largely reduce the updated redundancy.

关 键 词：最短路径 动态更新 路由算法 多节点 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]