An efficient time and space K point-to-point shortest simple paths algorithm

作者：Sedeno Noda Antonio^*

来源：Applied Mathematics and Computation, 2012, 218(20): 10244-10257.

DOI：10.1016/j.amc.2012.04.002

• Ranking best solutions
• Point-to-point shortest paths
• K best shortest simple paths

We address the problem identifying the K best point-to-point simple paths connecting a given pair of nodes in a directed network with arbitrary lengths. The main result in this paper is the proof that a path tree containing the kth point-to-point shortest simple path can be obtained by using one of the previous (k - 1) path trees containing each one of the previous (k - 1) best point-to-point shortest simple paths. The proof implies that at most n single-source shortest path computations (re-optimizations) in a network with non-negative length arcs are made in each iteration of the method. In the %26quot;optimistic%26apos;%26apos; case, this strategy only needs O(m) time to compute the best %26quot;neighbor%26apos;%26apos; associated with a path tree, that is, the second shortest simple path given a shortest simple path. The algorithm runs in O(Knf(n, m, C-max)) time and uses O(K + m) space to determine the K point-to-point shortest simple paths in a directed network with n nodes, m arcs and maximum absolute length Cmax. Here, O(f(n, m, C-max)) is the best time needed to determine the shortest simple paths connecting a source node with any other non-source node in a network with non-negative length arcs. We improve required space in Yen%26apos;s algorithm by a multiplicative factor of O(n(2)) for each best solution. Moreover, our algorithm runs in the %26quot;optimistic%26apos;%26apos; case in O(Kf (n, m, C-max)) time. This affirmation is confirmed by an experimental study where O(K) shortest paths are used to determine the K point-to-point shortest simple paths in two versions of our algorithm.

• 出版日期2012-6-15