Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs

摘要

Let G = (V, E) be a directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to find, for every edge e on P, a shortest path from s to t in G that avoids e. We present the first non-trivial algorithm for computing replacement paths in unweighted directed graphs (and in graphs with small integer weights). Our algorithm is Monte-Carlo and its running time is O(m n~(1/2)). Using the improved algorithm for the replacement paths problem we get an improved algorithm for finding the k simple shortest paths between two given vertices.