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

A construction algorithm of the stable shortest path tree

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