Efficient Dynamic Algorithm for Computation of Shortest Path Tree
Hong Qu · 2011
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.