基于背离路径的Kth最短路径实用搜索算法

• 作者: 傅俊伟 李兴明 陈捷
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: WDM光网络 Kth最短路径 背离路径
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 智能、算法、系统结构
• 页码范围: 120-122,126
• 页数: 4页
• 分类号: TP301.6
• 字数: 3762字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2009.02.034

摘要

基于背离路径的概念,设计Kth最短路径实用搜索算法.通过对第K-1最短路径求背离路径,求得第K最短路径.算法时间复杂度限制在O(e×n2),其中e为图的总边数,n为图的顶点数.在实时应用中,文中的算法有很好的应用前景.该算法已经成功应用到一个传输网络规划系统的动态RWA问题中.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李兴明	电子科技大学宽带光纤传输与通信网技术教育部重点实验室	29	220	8.0	13.0
2	陈捷		6	54	4.0	6.0
3	傅俊伟	电子科技大学宽带光纤传输与通信网技术教育部重点实验室	1	29	1.0	1.0