一种构建稳定的动态网络最短路径树的算法

摘要

本发明公开的一种构建稳定的动态网络最短路径树的算法，包含以下步骤：计算动态网络的初始的最短路径；统计动态网络中影响最短路径的不稳定边；通过减少不稳定边限制更新网络所需要的操作，构造稳定的最短路径树。本发明的算法，通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中，从而能够高效地减少边变化带来的操作。实验结果表明，与传统的动态最短路径树算法相比，本专利所提出的算法可以得到更稳定的最短路径树，并在更新时间上改进了57.24％，在结点更新次数上降低了43.6％。