一种基于光网络的搜索K最短路径的Yen改进算法

Yen improved algorithm for searching K-short path based on optical network

为提高K最短路径(KSP)算法中路径计算的效率和规划路径的相异性,首先介绍了光网络的图论描述、路径相近性定义和平行边的理论,然后对KSP问题和传统Yen算法进行了简单描述,分析了KSP算法研究现状,最后提出一种Yen改进算法,重点阐述了相异路径计算策略和Yen改进算法实现步骤。通过构建与实际生产环境类似的拓扑图,对Yen改进算法进行验证,并与其它算法进行路径相近性和计算时间对比,证明了其有效性。

In order to improve the efficiency of path calculation and the dissimilar of planning paths of K-short path(KSP)algorithm.First,this paper introduces the graph theory description of optical network,definition of path similarity and parallel edges theory.Then it describes the KSP problem and the traditional Yen algorithm briefly,and analyzes the research status of KSP algorithm.Finally,the paper proposes an Yen improved algorithm,and expounds the calculation strategy of dissimilar paths and the implementation steps of the improved algorithm emphatically.By constructing a topology map similar to the actual production environment,the Yen improved algorithm is verified,and the path proximity and calculation speed are compared with other algorithms to prove its effectiveness.