Computer Science ›› 2011, Vol. 38 ›› Issue (7): 96-99.
Previous Articles Next Articles
LIU Dai-bo,HOU Meng-shu,WU Ze-xu,QU Hong
Online:
Published:
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
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.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2011/V38/I7/96
Cited