计算机科学 ›› 2011, Vol. 38 ›› Issue (7): 96-99.
• 计算机网络与信息安全 • 上一篇 下一篇
刘代波,侯孟书,武泽旭,屈鸿
出版日期:
发布日期:
基金资助:
LIU Dai-bo,HOU Meng-shu,WU Ze-xu,QU Hong
Online:
Published:
摘要： 计算动态环境下最短路径树是一个典型的组合优化问题。Ba11-and-String模型是一种高效的动态更新算法，但仍存在不少冗余计算。针对Ba11-and-String算法中边的处理进行了优化，从而提高了动态更新的效率，同时实现了对节点的删除和增加，以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。
关键词: 动态计算，最短路径树，路由，算法
Abstract: The computation of shortest path tree in dynamic environment is a typical combinatorial optimization problem.Ball-and-String Model is an efficient algorithm which can dynamically update shortest path tree(SPT)，but exists redundant computation. This paper presented an a new dynamic SPT algorithm that optimizes the processing of edges in Ball-and-String Model. New algorithm raises the efficiency of dynamically updating SPT. Additionally, new algorithm implements deleting of node or adding of node in SPT, accordingly, can adjust for the topological variation of SPT. Experimental results show that new algorithm is more efficient than Ball-and-String Model.
Key words: Dynamic computing, Shortest path tree, Routing, Algorithm
刘代波,侯孟书,武泽旭,屈鸿. 一种高效的最短路径树动态更新算法[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/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2011/V38/I7/96
Cited
首页