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

来源：计算机工程与科学杂志2016年第3期北京时间：

作者：汪晓洁，郭文强，王思秀，蔡咏梅

单位：新疆财经大学计算机科学与工程学院,新疆 乌鲁木齐 830012

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

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

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