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

An efficient completely dynamic SPT algorithm

作　　者：汪晓洁[1] 郭文强[1] 王思秀[1] 蔡咏梅[1] 

机构地区：[1]新疆财经大学计算机科学与工程学院,新疆乌鲁木齐830012

出　　处：《计算机工程与科学》2016年第3期449-453,共5页Computer Engineering & Science

基　　金：国家自然科学基金(61163066);新疆高校科研计划青年教师科研启动基金(XJEDU2014S046);新疆财经大学科研基金(2015XYB007)

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

关 键 词：最短路径 SPF算法 动态更新 路由协议 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]