多链路权值增大的动态最短路径算法  

Dynamic Shortest Path Algorithm for Multi-link Increment

作　　者：肖乾才[1] 李明奇[1] 郭文强[2] 

机构地区：[1]电子科技大学数学科学学院,成都611731 [2]新疆财经大学计算机科学与工程学院,乌鲁木齐830012

出　　处：《计算机科学》2012年第4期114-117,122,共5页Computer Science

基　　金：中央高校基本科研业务费专项资金(ZYGX2009J101);国家自然科学基金(60902074)资助

摘　　要：动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(DSPT-MLI)。算法复杂度分析和仿真结果显示,DSPT-MLI算法具有更少的节点更新次数和更高的时间效率。Shortest path in dynamic network is one of important problems in transportation,communication system and so on.Dynamic shortest path algorithm for multi-link increment can significantly reduce the redundant computation compared with the dynamic algorithm for single link increment.At present,there has not any validated dynamic shortest path algorithm for multi-link increment.Based on the research on the present dynamic SPT algorithms,we proposed a dynamic SPT algorithm for multi-link increment（DSPT-MLI）.The complexity analysis of algorithm and simulation results show that DSPT-MLI requires less number of nodes to be updated and has higher efficiency.

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

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