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

J4 ›› 2016, Vol. 38 ›› Issue (03): 418-424.

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

杨晓花1,2，武继刚1,2，史雯隽1,2，赵国栋1,2

（1.天津工业大学计算机科学与软件学院，天津 300387;
2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190）

收稿日期:2015-03-17 修回日期:2015-05-21 出版日期:2016-03-25 发布日期:2016-03-25
基金资助:
国家自然科学基金(61173032);计算机体系结构国家重点实验室开放课题(CARCH201303）

A construction algorithm of the stable shortest path tree

YANG Xiaohua1,2,WU Jigang1,2,SHI Wenjun1,2,ZHAO Guodong1,2

（1.School of Computer Science and Software，Tianjin Polytechnic University，Tianjin 300387;
2.State Key Laboratory of Computer Architecture，
Institute of Computing Technology，Chinese Academy of Sciences,Beijing 100190,China）

Received:2015-03-17 Revised:2015-05-21 Online:2016-03-25 Published:2016-03-25

摘要/Abstract

摘要：

构建最短路径树是动态网络研究的重要问题之一。在动态网络中，当边状态发生变化时会引发最短路径树动态的重新构建，反复地计算不仅消耗大量时间，也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法，使得构造的路径树在动态网络上更稳定，即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中，从而能够高效地减少边变化带来的操作。实验结果表明，与传统的动态最短路径树算法相比，该算法可以得到更稳定的最短路径树，并且更新时间减少了5724%，结点更新次数降低了436%。

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

Abstract:

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%.

Key words: shortest path tree；dynamic network；reconstruct;stable

杨晓花1,2，武继刚1,2，史雯隽1,2，赵国栋1,2. 稳定的最短路径树及其构造算法[J]. J4, 2016, 38(03): 418-424.

YANG Xiaohua1,2,WU Jigang1,2,SHI Wenjun1,2,ZHAO Guodong1,2. A construction algorithm of the stable shortest path tree [J]. J4, 2016, 38(03): 418-424.