Abstract
The problem of finding multiple simple shortest paths in a weighted directed graph G=(V,E) has many applications, and is considerably more difficult than the corresponding problem when cycles are allowed in the paths. Even for a single source-sink pair, it is known that two simple shortest paths cannot be found in time polynomially smaller than n^3 (where n=|V|) unless the All-Pairs Shortest Paths problem can be solved in a similar time bound. We consider the all-pairs version of the problem, and we give a new algorithm to find k simple shortest paths for all pairs of vertices. For k=2, our algorithm runs in O(mn + n^2 log n) time (where m=|E|), which is almost the same bound as for the single pair case, and for k=3 we improve earlier bounds. Our results are based on forming suitable path extensions to find simple shortest paths; this method is different from the `detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. We also present algorithms to find $k$ simple cycles through a vertex and $k$ simple cycles through all vertices.
Enumerating simple cycles is a classical well-studied problem. We present a new \tilde-O(mn) time algorithm to enumerate each successive simple shortest cycle in non-decreasing order of weight.
We show that all of the above problems are at least as hard as finding a minimum weight cycle in an O(n)-node, O(m)-edge graph. In contrast to this result, we give a new algorithm, again through suitable path extensions, that enumerates each successive simple path in nondecreasing order of weight in near linear time.
Joint work with Udit Agarwal.