Donald Bren School of Information and Computer Sciences

We describe algorithms for finding the k shortest paths connecting a given pair of vertices in a digraph (allowing cycles). Our algorithms output an implicit representation of the paths as an unordered set in time O(m + n log n + k). The paths can be output in order by length in total time O(m + n log n + k log k). We can also find the k paths from a given source s to each vertex in the graph, in total time O(m + n log n + kn).