关于k次短路径问题的分析与求解  

A kth-shortest Path Algorithm Based on k-1 Shortest Paths

作　　者：白轶多[1,2] 胡鹏[1,2] 夏兰芳[1,2] 郭峰林[1,2] 

机构地区：[1]武汉大学资源与环境科学学院,武汉市珞喻路129号430079 [2]武汉大学地理信息系统教育部重点实验室,武汉市珞喻路129号430079

出　　处：《武汉大学学报（信息科学版）》2009年第4期492-494,共3页Geomatics and Information Science of Wuhan University

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

摘　　要：分析了前k条最短路径的图论理论基础,在计算出最短路径的基础上,提出了一种基于前k-1条最短路径的k次短路径的求解方法,该方法能方便高效地找出次短路、再次短路,一直到k次短路。该算法的时间复杂度为O(n2),可以很好地满足实际应用需要。k shortest paths include the shortest one, the second shortest one, the third shortest one, and soon. After analyzed k shortest paths problems with graph theory, the kthshortest path algorithm was designed and analyzed based on k-1 shortest paths. The algorithm is more efficient than others.

关 键 词：最短路径 k次短路径 网络分析 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论] O157.5[自动化与计算机技术—计算机科学与技术]