关于k次短路径问题的分析与求解
A kth-shortest Path Algorithm Based on k-1 Shortest Paths
-
摘要: 分析了前k条最短路径的图论理论基础,在计算出最短路径的基础上,提出了一种基于前k-1条最短路径的k次短路径的求解方法,该方法能方便高效地找出次短路、再次短路,一直到k次短路。该算法的时间复杂度为O(n2),可以很好地满足实际应用需要。Abstract: 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 kth-shortest path algorithm was designed and analyzed based on k-1 shortest paths.The algorithm is more efficient than others.
下载:
