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