@Bibtex-file{Theory/k-path.bib,
title = "Bibliography on algorithms for k shortest paths",
author = "David Eppstein",
address = "Dept. of Information and Computer Science\\ University
of California\\ Irvine, CA 92717-3425\\USA",
email = "eppstein@ics.uci.edu",
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.
\begin{enumerate}\item 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. \item 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. \end{enumerate}",
keywords = "shortest paths, k shortest paths, k most vital arcs,
dynamic programming, sequence alignment, knapsack
problem, k minimum spanning trees",
}