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

34 4 # Vol. 34 No. 4 2009 4 Geomatics and Informat ion Science of Wuhan University A r. 2009 : 1671-8860(2009) 04-0492-03 : A 关于k 次短路径问题的分析与求解 1, 2 1, 2 1, 2 1, 2 白轶多 胡 鹏 夏兰芳 郭峰林 ( 1 , 129 , 430079) ( 2 , 129 , 430079) :分析了前k 条最短路径的图论理论基础, 在计算出最短路径的基础上, 提出了一种基于前k - 1 条最 短路径的k 次短路径的求解方法, 该方法能方 高效地找出次短路再次短路, 一直到k 次短路该算法的时 2 间复杂度为O( n ) , 可以很好地满足实际应用需要 : 最短路径; k 次短路径; 网络分析 : , Dijkstra v s , d i v i [ 5] ( ) : ¹ v s , dij v i vj ; º , d (s, e, t) v e v s , v t , Dk k , D 1= de , , v5 v7 v 10 v 13 v 14 v 15 v 17 v 1-v 9- , v 11-v 16 , 结论1 , v i vj d ji \di - dj ; vi vj d ij = di - dj k 结论2 , , Dijkstra N , : [ 2] [ 3] , k , k ( [ D2 = min ( di + dji + D 1 - dj ) ( 1) i I V ,j I V [ 4] n 1 3) , , Vn ; V1 , ; D 1 , N 结论3 k k - 1 , , : , N k i ij h j