  Let $G$ be a directed graph with $n$ vertices, $m$ edges, and non-negative
edge costs. Given $G$, a fixed source vertex $s$, and a positive integer $p$,
we consider the problem of computing, for each vertex $t\neq s$, $p$
edge-disjoint paths of minimum total cost from $s$ to $t$ in $G$. Suurballe and
Tarjan~[Networks, 1984] solved the above problem for $p=2$ by designing a
$O(m+n\log n)$ time algorithm which also computes a sparse \emph{single-source
$2$-multipath preserver}, i.e., a subgraph containing $2$ edge-disjoint paths
of minimum total cost from $s$ to every other vertex of $G$. The case $p \geq
3$ was left as an open problem.
  We study the general problem ($p\geq 2$) and prove that any graph admits a
sparse single-source $p$-multipath preserver with $p(n-1)$ edges. This size is
optimal since the in-degree of each non-root vertex $v$ must be at least $p$.
Moreover, we design an algorithm that requires $O(pn^2 (p + \log n))$ time to
compute both $p$ edge-disjoint paths of minimum total cost from the source to
all other vertices and an optimal-size single-source $p$-multipath preserver.
The running time of our algorithm outperforms that of a natural approach that
solves $n-1$ single-pair instances using the well-known \emph{successive
shortest paths} algorithm by a factor of $\Theta(\frac{m}{np})$ and is
asymptotically near optimal if $p=O(1)$ and $m=\Theta(n^2)$. Our results extend
naturally to the case of $p$ vertex-disjoint paths.
