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

摘要

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 “optimistic” case, this strategy only needs O(m) time to compute the best “neighbor” associated with a path tree, that is, the second shortest simple path given a shortest simple path. The algorithm runs in O(K nf(n, m, Cmax)) 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, Cmax)) 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’s algorithm by a multiplicative factor of O(n2) for each best solution. Moreover, our algorithm runs in the “optimistic” case in O(Kf (n, m, Cmax)) 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.