Key points are not available for this paper at this time.
A general procedure is presented for computing the best, 2nd best,…, Kth best solutions to a given discrete optimization problem. If the number of computational steps required to find an optimal solution to a problem with n(0, 1) variables is c(n), then the amount of computation required to obtain the if best solutions is O(K nc (n)). The procedure specializes to published procedures of Murty and of Yen for the assignment problem and the shortest path problem, respectively. A method is presented for reducing the required amount of storage by a factor of n, compared with the algorithms of Murty and of Yen. It is shown how the K shortest (loopless) paths in an n-node network with positive and negative arcs can be computed with an amount of computation which is O(Kn 3 ). This represents an improvement by a factor of n, compared with Yen's algorithm.
Eugene L. Lawler (Wed,) studied this question.