Finding the $k$ shortest paths

David Eppstein

*SIAM J. Computing* 28(2):652–673, 1998

*Mathematical Reviews* 99h:05073, 1999

Reviewed by Koduvayur R. Parthasarathy

The $k$-shortest-paths problem is to list the $k$ paths from a specified source $s$ to a specified destination $t$ in a digraph, with minimum total length. The author considers digraphs admitting self-loops, multiple edges and cycles without negative lengths, and the paths are not necessarily simple. Using an implicit representation of the paths, the author presents, in detail, an algorithm with time complexity $O(m+n\log n+k)$ where $n$ and $m$ are the number of vertices and the number of edges of the digraph. This also leads to an algorithm of complexity $O(m+n\log n+kn)$ for the $k$-shortest-paths problem from a given source $s$ to all other vertices of the graph. To get the implicit representation, one starts with a single-destination $(t)$ shortest path tree $T$ of the given digraph $G$ with source $s$ and destination $t$ and produces a heap $H\sb G(v)$ at each vertex $v$ leading to a directed acyclic graph $D(G)$ and through that to a path graph $P(G)$, with the property that there is a one-to-one "length-preserving" correspondence between $s$-$t$ paths in $G$ and paths starting from the root $r$ in $P(G)$ and finally to a 4-heap $H(G)$ whose nodes correspond to the $s$-$t$ paths of $G$. After developing a basic algorithm, improvements are introduced in the heap construction to attain the above complexity. The improvements in time complexity achieved through this algorithm when used for the dynamic programming applications to the following optimization problems are discussed at some length: the knapsack problem, sequence alignment, inscribed polygons, and genealogical relations. Three open problems are suggested.