Multiple Source Replacement Path Problem

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 O (m + n) time1. It is natural to ask whether we can generalize the replacement path problem: 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.