改进的K最短路径算法在通信网络中的应用  

A New Fault-Tolerance Mechanism in Communications Based on KShortest Path Algorithm

作　　者：毛少武[1] 张焕国[1] 黄崇超[2] 吴万青[1] 

机构地区：[1]武汉大学计算机学院/空天信息安全与可信计算教育部重点实验室,湖北武汉430072 [2]武汉大学数学与统计学院,湖北武汉430072

出　　处：《武汉大学学报（理学版）》2013年第6期534-538,共5页Journal of Wuhan University:Natural Science Edition

基　　金：国家自然科学基金(91018008;61003268)资助项目

摘　　要：经典的K最短路径算法是最短路径算法中一个重要分支,它在交通网络的实时路径选择中起到了很重要的作用,为了将经典的K最短路径算法应用于通信网络中,我们对经典的K最短路径算法进行了改进.在求解K最大期望容量路径算法时,先对其进行权重转换,然后使用MPS算法;在求解K最大容量路径算法时,选取每个弧段源点,终点和弧段对应3个容量值最大的来进行标号;在求解K最大期望容量路径时,建立一系列的子网络,在每个子网络中先求出K最大可靠路径,对其容量进行排序,选出最小的,将大于该最小容量的所有弧集构成的网络定义为它的子网络,以此类推直到源点到目标点没有路径为止,对每个子网络中选取的K最大期望容量路径进行统一排序得到原网络中的K最大期望路径.通过网络通信实例,验证了算法的正确性和可行性.Classic Kshortest path algorithm is an important branch of the shortest path algorithm,which plays a very important role in path choosing of the real-time traffic network.In order to apply classic Kshortest path algorithm to communication networks,we improved the classic Kshortest path algorithm.When finding the K maximum capacity paths,transform network at first,then use MPS algorithm;to find K maximum capacity path,choose the maximum capacity correspond to source,destination,and arcs for labels;to find K maximum expected capacity path,we create a series of sub-networks for each sub-network to find the most dependable path at first,to sort their capacity to get the smallest,then all arcs whose capacity is greater than the smallest is defined as a sub-network of this subnetwork,until there is no paths from the source point to the target point.Then order them entirely for K maximum expected capacity path of each sub-network to get the K maximum expected path,and then through a network communication example to verify the correctness and feasibility of the algorithms.

关 键 词：物联网 K最短路 MPS算法 K最大期望容量路径 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]