摘要： 现有的动态最短路径树算法在某些边的权值频繁变化时,会造成动态网络中的最短路径树频繁更新,而且当网络中的路由器毁坏或增加新的路由器时,该算法难于应用到构造最短路径树中。针对上述问题,提出一种最短路径树的维护算法。对权值频繁变化的边进行处理,避免将其加入到最短路径树中,减少最短路径树的更新次数,当网络中的路由器毁坏或者增加时,通过减少冗余边的入队操作,对网络中的最短路径树进行维护。实验结果表明,与高效的最短路径树动态更新算法相比,该算法的更新时间效率更高。

关键词: 动态网络, 最短路径树, 路由器, 动态最短路径树算法, 维护算法

Abstract: The reported Dynamic Shortest Path Tree(DSPT) algorithm can result in frequent update of the Shortest Path Tree(SPT) in dynamic network when the weight of some edges frequently change.And when a router is destroyed or a new router is added into the network,the algorithm is not applicable for constructing the SPT.Aiming at the above problems,an effective maintenance algorithm for SPT is proposed,which can greatly reduce the update of the SPT through dealing with the frequently changed weight of some edges by excluding the unstable edges from the SPT.At the same time,when a router is destroyed or added into the network,the SPT can be effectively maintained in the network through reducing the redundant edge enqueue operation.Experimental results show that compared with efficient dynamic algorithm for computation of SPT,the algorithm’s update time is more efficient.

Key words: dynamic network, Shortest Path Tree(SPT), router, Dynamic Shortest Path Tree(DSPT) algorithm, maintenance algorithm

中图分类号: 

• TP399