  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. The
latter is a well-known open problem in algorithm design. 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 approach
is 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.
  Enumerating simple cycles is a well-studied classical problem. We present new
algorithms for generating simple cycles and simple paths in $G$ in
non-decreasing order of their weights; the algorithm for generating simple
paths is much faster, and uses another variant of path extensions. We also give
hardness results for sparse graphs, relative to the complexity of computing a
minimum weight cycle in a graph, for several variants of problems related to
finding $k$ simple paths and cycles.
