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

在通信网络中,节点间最短路径的计算是链路状态路由协议计算路由的基础。通过对现有动态最短路径算法的深入研究,提出了一种处理网络拓扑变化的完全动态最短路径算法DSPT-ID。该算法利用已有SPT的信息,建立一个最短路径树的更新队列,当网络拓扑发生变化时,算法针对边的权值增大和减小,分别进行更新,并将更新节点局限在受拓扑变化影响的节点中,从而达到SPT的增量更新。算法复杂度分析和仿真结果显示,DSPT-ID算法具有更少的节点更新次数和更高的时间效率。

An efficient completely dynamic SPT algorithm

Computation of the shortest path between two nodes in communication networks is the basis of the link state routing protocol. Based on the study on the present dynamic SPT algorithms, we propose a new completely dynamic SPT algorithm (DSPT ID) for handling network topology changing. This algorithm establishes an SPT update queue and pays attention only to the changes of nodes and edges by making use of information provided by the existing SPT, which can achieve incremental update. When the topology of the network changes, the increase or decrease of edge weights can be processed by the DSPT ID algorithm. The analysis of algorithm complexity and simulation results show that the DSPT ID requires less update of nodes and has higher efficiency.