摘要: 计算动态环境下最短路径树是一个典型的组合优化问题。Ba11-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算。针对Ba11-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。
刘代波,侯孟书,武泽旭,屈鸿. 一种高效的最短路径树动态更新算法[J]. 计算机科学, 2011, 38(7): 96-99. https://doi.org/
LIU Dai-bo,HOU Meng-shu,WU Ze-xu,QU Hong. Efficient Dynamic Algorithm for Computation of Shortest Path Tree[J]. Computer Science, 2011, 38(7): 96-99. https://doi.org/