Shortest paths avoiding forbidden subpaths

AbstractWe study a variant of the shortest path problem in graphs: given a weighted graph Gand vertices sand t, and given a set Xof forbidden paths in G, find a shortest s‐ tpath Psuch that no path in Xis a subpath of P. Path Pis allowed to repeat vertices and edges. We call each path in Xan exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x∈Xonly when a path containing xfails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The main idea is to use a shortest path algorithm incrementally after replicating vertices when an exception is discovered. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013