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

摘要：

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

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

所属期刊栏目：38

分类号：TP393(计算技术、计算机技术)

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

在线出版日期：2016-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：418-424