摘要
提出一种更新移动目标最短路径树的近似算法来避免重新生成整棵路径树。算法使用了局部图的思想,使每次迭代更新尽量少的节点来减少代价。实验证明算法具有良好的效率、近似度和可伸缩性。分析了如何调整算法,以便在近似度和效率之间实现平衡。
This paper presents an approximate algorithm for updating the shortest path tree of moving target to avoid regenerate the whole tree. Based on the concept of Local map, the algorithm tries to update as few nodes as possible to reduce cost. The experimental results demonstrate that the new algorithm deserves good efficiency, approximation and scalabilities. Furthermore, we show how to reach the trade-off between efficiency and approximation.
出处
《计算机科学》
CSCD
北大核心
2006年第11期222-224,共3页
Computer Science
基金
国家863计划(No.2002AA413310
No.2003AA4Z2170
No.2003A413021)
关键词
移动目标
单源最短路径树
近似算法
局部图
Moving target, Single-source shortest path tree, Approximate algorithms, Local map
