k最短可靠路径及其优化问题  

k-shortest reliable paths and its optimization

作　　者：张震霄 管建民 邵方明[1] ZHANG Zhenxiao;GUAN Jianmin;SHAO Fangming(East China University of Science and Technology,Shanghai 200237,China;Department of Mathematics Teaching and Research,Changchun University of Finance and Economics,Changchun 130122,China)

机构地区：[1]华东理工大学,上海200237 [2]长春财经学院数学教研部,吉林长春130122

出　　处：《现代电子技术》2020年第23期58-61,共4页Modern Electronics Technique

基　　金：国家自然科学基金资助项目(61040040)。

摘　　要：k最短路径在边失效模型中,存在一个等长路径的选择问题,基于可靠性的选择是有效的解决方案。这里提出了一种k最短路径限制下的可靠性模型来度量k最短路径,进一步把等长路径的选择问题转化为一个可靠性优化问题,即选择使得可靠性最大的k最短路径。最终通过设计近似算法有效地解决了优化问题,实例证明了该算法的有效性。In the edge failure model,it is required to select paths with equal length for the k-shortest paths.The reliabilitybased selection is an effective solution.In this paper,a reliability model under the constraint of k-shortest paths is proposed to measure the k-shortest paths,and convert the selection of paths with equal length to the optimization of the paths,that is,to choose the k-shortest paths with maximum reliability.In the end,an approximate algorithm is designed to realize the optimization effectively.The examples shows the effectiveness of the algorithm.

关 键 词：网络可靠性 k最短可靠路径 子网络 路径优化 优化策略 边失效模型 

分 类 号：TN711-34[电子电信—电路与系统]