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

摘要：

计算动态环境下最短路径树是一个典型的组合优化问题.Ball-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算.针对Ball-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化.实验结果表明新算法效率更高.

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

所属期刊栏目：38

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

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

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

页数：共4页

页码：96-99