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

Efficient Dynamic Algorithm for Computation of Shortest Path Tree

作　　者：刘代波[1] 侯孟书[1] 武泽旭[2] 屈鸿[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610000 [2]四川大学电气信息学院,成都610000

出　　处：《计算机科学》2011年第7期96-99,共4页Computer Science

基　　金：国家自然科学基金(60905037);电子科技大学青年基金(L08010601)资助

摘　　要：计算动态环境下最短路径树是一个典型的组合优化问题。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.

关 键 词：动态计算 最短路径树 路由 算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]