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

被引：11

作者：

傅俊伟 ^{[1
]}

李兴明 ^{[1
]}

陈捷 ^{[2
]}

机构：

[1] 电子科技大学宽带光纤传输与通信网技术教育部重点实验室

[2] 中兴通讯股份有限公司

来源：

关键词：

WDM光网络; Kth最短路径; 背离路径;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：120 / 122+126 +126

页数：4

共 5 条

[1] 一种新的Kth最短路径搜索算法 [J].

王明中 ;

谢剑英 ;

陈应麟 ;

不详 .

[2] 前N条最短路径问题的算法及应用 [J].

柴登峰 ;

张登荣 .

[3] WDM光传送网的选路和波长分配算法 [J].

李乐民 .

[4] Provisioning algorithms for WDM optical networks [J].

Alanyali, M ;

Ayanoglu, E .

[5] Adaptive wavelength routing in all-optical networks [J].

Mokhtar, A ;

Azizoglu, M .