Approximate Algorithms for Updating Single-Source Shortest Path Tree of Moving Target
移动目标单源最短路径树更新的近似算法

This paper presents an approximate algorithm for updating the shortest path tree of moving target to avoid re-generate 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.