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

Dynamic node remove algorithm based on routing shortest path tree

提出一种基于最短路径树的节点删除动态路由算法。算法建立一个最短路径树更新集合,该集合包括被删除节点的断裂子树所有节点和其它节点连接的边,利用子树的结构信息,对子树节点的直系子孙节点和祖先节点进行更新,采用Dijkstra算法对其它子树节点进行更新。实验结果表明,该算法能有效减少节点更新计算次数。

A new node removing dynamic algorithm based on routing Shortest Path Tree（SPT） is proposed.First,it establi-shes an updating set of shortest path tree.The set includes all edges connecting nodes of breaking subtree and other nodes of graph.Then,it takes advantage of structural information of the subtree and Dijkstra algorithm to update nodes of the sub-tree.Experimental result shows that this algorithm can largely reduce the updated frequency.