计算机科学 ›› 2011, Vol. 38 ›› Issue (7): 96-99.

• 计算机网络与信息安全 • 上一篇    下一篇

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

刘代波,侯孟书,武泽旭,屈鸿   

  1. (电子科技大学计算机科学与工程学院 成都610000);(四川大学电气信息学院 成都610000)
  • 出版日期:2018-11-16 发布日期:2018-11-16
  • 基金资助:
    本文受国家自然科学基金(60905037),电子科技大学青年基金(L08010601)资助。

Efficient Dynamic Algorithm for Computation of Shortest Path Tree

LIU Dai-bo,HOU Meng-shu,WU Ze-xu,QU Hong   

  • Online:2018-11-16 Published:2018-11-16

摘要: 计算动态环境下最短路径树是一个典型的组合优化问题。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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!