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

摘要

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.%提出一种基于路由最短路径树的多节点删除动态算法.算法建立一个最短路径树更新队列,将所有将被删除节点的子孙节点保存到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,已更新节点不再被插入队列,从而减少节点更新次数.实验结果表明,该算法能有效减少节点的更新冗余.