  One of the classical line of work in graph algorithms has been the
Replacement Path Problem: given a graph $G$, $s$ and $t$, find shortest paths
from $s$ to $t$ avoiding each edge $e$ on the shortest path from $s$ to $t$.
These paths are called replacement paths in literature. For an undirected and
unweighted graph, (Malik, Mittal, and Gupta, Operation Research Letters, 1989)
and (Hershberger and Suri, FOCS 2001) designed an algorithm that solves the
replacement path problem in $\tilde O(m+n)$ time. It is natural to ask whether
we can generalize the replacement path problem: {\em can we find all
replacement paths from a source $s$ to all vertices in $G$?} This problem is
called the Single Source Replacement Path Problem.
  Recently (Chechik and Cohen, SODA 2019) designed a randomized combinatorial
algorithm that solves the Single Source Replacement Path Problem in $\tilde
O(m\sqrt n\ + n^2)$ time. One of the questions left unanswered by their work is
the case when there are many sources, not one. When there are $n$ sources, the
combinatorial algorithm of (Bernstein and Karger, STOC 2009) can be used to
find all pair replacement path in $\tilde O(mn + n^3)$ time. However, there is
no result known for any general $\sigma$. Thus, the problem we study is defined
as follows: given a set of $\sigma$ sources, we want to find the replacement
path from these sources to all vertices in $G$. We give a randomized
combinatorial algorithm for this problem that takes $\tilde O(m\sqrt{n \sigma}
+\ \sigma n^2)$ time. This result generalizes both results known for this
problem. Our algorithm is much different and arguably simpler than (Chechik and
Cohen, SODA 2019). Like them, we show a matching conditional lower bound using
the Boolean Matrix Multiplication conjecture.
