A Simple Algorithm For Replacement Paths Problem

Let G=(V,E)G=(V,E) (|V|=n|V|=n and |E|=m|E|=m) be an undirected graph with positive edge weights. Let PG(s,t)PG(s,t) be a shortest s−ts−t path in G. Let l   be the number of edges in PG(s,t)PG(s,t). The Edge Replacement Path   problem is to compute a shortest s−ts−t path in G\{e}G\{e}, for every edge e   in PG(s,t)PG(s,t). The Node Replacement Path   problem is to compute a shortest s−ts−t path in G\{v}G\{v}, for every vertex v   in PG(s,t)PG(s,t).In this paper we present an O(TSPT(G)+m+l2)O(TSPT(G)+m+l2) time and O(m+l2)O(m+l2) space algorithm for both the problems. Where, TSPT(G)TSPT(G) is the asymptotic time to compute a single source shortest path tree in G. The proposed algorithm is simple and easy to implement.