稳定的最短路径树及其构造算法  

A construction algorithm of the stable shortest path tree

作　　者：杨晓花[1,2] 武继刚[1,2] 史雯隽 赵国栋[1,2] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190

出　　处：《计算机工程与科学》2016年第3期418-424,共7页Computer Engineering & Science

基　　金：国家自然科学基金(61173032);计算机体系结构国家重点实验室开放课题(CARCH201303)

摘　　要：构建最短路径树是动态网络研究的重要问题之一。在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作。实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24%,结点更新次数降低了43.6%。Constructing the shortest path tree is an important problem in dynamic networks,in which the changed edges will lead to dynamic reconstruction of the shortest path tree.Repeated calculation not only consumes a lot of time,but also results in frequent changes of the shortest path tree.We propose an algorithm for constructing the stable shortest path tree,which takes fewer update operations on nodes.The algorithm updates the shortest path tree by excluding the unstable edges so as to effectively reduce the number of the update operations.Experimental results show that compared with traditional dynamic network shortest path tree algorithms,the proposed algorithm can generate relatively more stable shortest path tree.The update time is improved by 57.24%,and the number of update operations on nodes is reduced by 43.6%.

关 键 词：最短路径树 动态网络 重新构建 稳定的 

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