| 多链路权值增大的动态最短路径算法 |
| |
| 引用本文： | 肖乾才,李明奇,郭文强.多链路权值增大的动态最短路径算法[J].计算机科学,2012,39(4):114-117,122. |
| |
| 作者姓名： | 肖乾才 李明奇 郭文强 |
| |
| 作者单位： | 1. 电子科技大学数学科学学院 成都611731
2. 新疆财经大学计算机科学与工程学院 乌鲁木齐830012 |
| |
| 基金项目： | 中央高校基本科研业务费专项资金项目，国家自然科学基金 |
| |
| 摘 要： | 动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(DSPT-MLI)。算法复杂度分析和仿真结果显示,DSPT-MLI算法具有更少的节点更新次数和更高的时间效率。
|
| 关 键 词： | 动态最短路径 SPF算法 路由协议 最短路径树 |
Dynamic Shortest Path Algorithm for Multi-link Increment |
| |
| XIAO Qian-cai
,
LI Ming-qi
,
GUO Wen-qiang.Dynamic Shortest Path Algorithm for Multi-link Increment[J].Computer Science,2012,39(4):114-117,122. |
| |
| Authors: | XIAO Qian-cai LI Ming-qi GUO Wen-qiang |
| |
| Affiliation: | 2 (School of Mathematical Sciences,University of Electronic Science and Technology of China,Chengdu 611731,China)1(School of Computer Science and Engineering,Xinjiang University of Finance & Economics,Wulumuqi 830012,China)2 |
| |
| Abstract: | 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. |
| |
| Keywords: | Dynamic shortest path SPF algorithm Route protocol Shortest path tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
