David Eppstein <eppstein @ ics . uci . edu> (email mangled to prevent spamming)
Dept. of Information and Computer Science University of California Irvine, CA 92717-3425 USA
Abstract:
This bibliography lists papers studying a generalization of the shortest path problem: not just finding the single shortest path between a pair of nodes, but instead listing a sequence of the k shortest paths. Methods for finding k shortest paths have been applied to many applications, for two reasons.
One may wish to find a path that satisfies certain constraints beyond having a small length, but those other constraints may be ill-defined or hard to optimize. A typical solution is to compute several short paths and then choose among them by considering the other criteria.
By computing more than one shortest path, one can determine how sensitive the optimal solution is to variation of the problem's parameters. The bibliography also includes related work on listing k best solutions to other combinatorial problems.
Keywords:
shortest paths, k shortest paths, k most vital arcs, dynamic programming, sequence alignment, knapsack problem, k minimum spanning trees
