A simplification of the double-sweep algorithm to solve the k-shortest path problem

In this paper, we define the k-shortest path problem, which will be used to model the problem of routing aircraft through a network of airfields. This problem finds the optimal alternative routes from one or more origins to one or more destinations. We solve this problem using the double-sweep algorithm. We present a simplification to the double-sweep algorithm, and show that this simplification reduces the computational complexity of the algorithm by a factor of k. We prove that the simplified double-sweep algorithm converges. Finally, we demonstrate this algorithm on a small airlift network. (C) 2000 Elsevier Science Ltd. All rights reserved.