  In the Single Source Replacement Paths (SSRP) problem we are given a graph $G
= (V, E)$, and a shortest paths tree $\widehat{K}$ rooted at a node $s$, and
the goal is to output for every node $t \in V$ and for every edge $e$ in
$\widehat{K}$ the length of the shortest path from $s$ to $t$ avoiding $e$.
  We present an $\tilde{O}(m\sqrt{n} + n^2)$ time randomized combinatorial
algorithm for unweighted directed graphs. Previously such a bound was known in
the directed case only for the seemingly easier problem of replacement path
where both the source and the target nodes are fixed.
  Our new upper bound for this problem matches the existing conditional
combinatorial lower bounds. Hence, (assuming these conditional lower bounds)
our result is essentially optimal and completes the picture of the SSRP problem
in the combinatorial setting.
  Our algorithm extends to the case of small, rational edge weights. We
strengthen the existing conditional lower bounds in this case by showing that
any $O(mn^{1/2-\epsilon})$ time (combinatorial or algebraic) algorithm for some
fixed $\epsilon >0$ yields a truly subcubic algorithm for the weighted All
Pairs Shortest Paths problem (previously such a bound was known only for the
combinatorial setting).
