Let G=(V,E) be an n -vertices m -edges directed graph with edge weights in the range [1, W ] for some parameter W , and sϵ V be a designated source. In this article, we address several variants of the problem of maintaining the (1+ε)-approximate shortest path from s to each v ϵ V { s } in the presence of a failure of an edge or a vertex. From the graph theory perspective, we show that G has a subgraph H with Õ(ε -1 } n log W ) edges such that for any x,vϵ V , the graph H \ x contains a path whose length is a (1+ε)-approximation of the length of the shortest path from s to v in G \ x . We show that the size of the subgraph H is optimal (up to logarithmic factors) by proving a lower bound of Ω (ε -1 n log W ) edges. Demetrescu, Thorup, Chowdhury, and Ramachandran (SICOMP 2008) showed that the size of a fault tolerant exact shortest path subgraph in weighted directed/undirected graphs is Ω ( m ). Parter and Peleg (ESA 2013) showed that even in the restricted case of unweighted undirected graphs, the size of any subgraph for the exact shortest path is at least Ω ( n 1.5 ). Therefore, a (1+ε)-approximation is the best one can hope for. We consider also the data structure problem and show that there exists an ϕ(ε -1 n log W ) size oracle that for any vϵ V reports a (1+ε)-approximate distance of v from s on a failure of any xϵ V in O(log log 1+ε ( nW )) time. We show that the size of the oracle is optimal (up to logarithmic factors) by proving a lower bound of Ω (ε -1 n log W log -1 n ). Finally, we present two distributed algorithms . We present a single-source routing scheme that can route on a (1+ε)-approximation of the shortest path from a fixed source s to any destination t in the presence of a fault. Each vertex has a label and a routing table of ϕ(ε -1 log W ) bits. We present also a labeling scheme that assigns each vertex a label of ϕ(ε -1 log W ) bits. For any two vertices x,vϵ V , the labeling scheme outputs a (1+ε)-approximation of the distance from s to v in G \ x using only the labels of x and v .

Let G = (V, E) be an n-vertices m-edges directed graph with edge weights in the range [1, W] and L = log(W). Let s ∊ V be a designated source. In this paper we address several variants of the problem of maintaining the (1 + ∊)-approximate shortest path from s to each υ ∊ V \ {s} in the presence of a failure of an edge or a vertex. From the graph theory perspective we show that G has a subgraph H with Õ(nL/∊) edges such that for any x,υ ∊ V, the graph H \ x contains a path whose length is a (1 + ∊)-approximation of the length of the shortest path from s to υ in G \ x. We show that the size of the subgraph H is optimal (up to logarithmic factors) by proving a lower bound of Ω(nL/∊) edges. Demetrescu, Thorup, Chowdhury and Ramachandran [12] showed that the size of a fault tolerant exact shortest path subgraph in weighted directed/undirected graphs is Ω(m). Parter and Peleg [18] showed that even in the restricted case of unweighted undirected graphs the size of any subgraph for the exact shortest path is at least Ω(n1.5). Therefore, a (1 + ∊)-approximation is the best one can hope for. We consider also the data structure problem and show that there exists an Õ(nL/∊) size oracle that for any υ ∊ V reports a (1 + ∊)-approximate distance of v from s on a failure of any x ∊ V in O(loglog1+∊(nW)) time. We show that the size of the oracle is optimal (up to logarithmic factors) by proving a lower bound of Ω(nL/∊ log n). Finally, we present two distributed algorithms. We present a single source routing scheme that can route on a (1 + ∊)-approximation of the shortest path from a fixed source s to any destination t in the presence of a fault. Each vertex has a label and a routing table of Õ(L/∊) bits. We present also a labeling scheme that assigns each vertex a label of Õ(L/∊) bits. For any two vertices x, υ ∊ V the labeling scheme outputs a (1 + ∊)-approximation of the distance from s to υ in G\x using only the labels of x and v.