一种高效的最短路径树动态更新算法

Efficient Dynamic Algorithm for Computation of Shortest Path Tree

计算动态环境下最短路径树是一个典型的组合优化问题。Ball-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算。针对Ball-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。

The computation of shortest path tree in dynamic environment is a typical combinatorial optimization problem.Ball-and-String Model is an efficient algorithm which can dynamically update shortest path tree（SPT）,but exists redundant computation.This paper presented an a new dynamic SPT algorithm that optimizes the processing of edges in Ball-and-String Model.New algorithm raises the efficiency of dynamically updating SPT.Additionally,new algorithm implements deleting of node or adding of node in SPT,accordingly,can adjust for the topological variation of SPT.Experimental results show that new algorithm is more efficient than Ball-and-String Model.