移动目标单源最短路径树更新的近似算法

摘要：

提出一种更新移动目标最短路径树的近似算法来避免重新生成整棵路径树.算法使用了局部图的思想,使每次迭代更新尽量少的节点来减少代价.实验证明算法具有良好的效率、近似度和可伸缩性.分析了如何调整算法,以便在近似度和效率之间实现平衡.

关键词：移动目标、单源最短路径树、近似算法、局部图

所属期刊栏目：33

分类号：TP3(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划2002AA413310;2003AA4Z2170;2003A413021

在线出版日期：2006-12-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：222-224