  Given an $n$-vertex undirected graph $G=(V,E,w)$, and a parameter $k\geq1$, a
path-reporting distance oracle (or PRDO) is a data structure of size $S(n,k)$,
that given a query $(u,v)\in V^2$, returns an $f(k)$-approximate shortest $u-v$
path $P$ in $G$ within time $q(k)+O(|P|)$. Here $S(n,k)$, $f(k)$ and $q(k)$ are
arbitrary functions.
  A landmark PRDO due to Thorup and Zwick, with an improvement of Wulff-Nilsen,
has $S(n,k)=O(k\cdot n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(\log k)$. The
size of this oracle is $\Omega(n\log n)$ for all $k$. Elkin and Pettie and
Neiman and Shabat devised much sparser PRDOs, but their stretch was
polynomially larger than the optimal $2k-1$. On the other hand, for
non-path-reporting distance oracles, Chechik devised a result with
$S(n,k)=O(n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(1)$.
  In this paper we make a dramatic progress in bridging the gap between
path-reporting and non-path-reporting distance oracles. We devise a PRDO with
size $S(n,k)=O(\lceil\frac{k\log\log n}{\log n}\rceil\cdot n^{1+\frac{1}{k}})$,
stretch $f(k)=O(k)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log
n}\rceil)$. We can also have size $O(n^{1+\frac{1}{k}})$, stretch
$O(k\cdot\lceil\frac{k\log\log n}{\log n}\rceil)$ and query time
$q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$.
  Our results on PRDOs are based on novel constructions of approximate distance
preservers, that we devise in this paper. Specifically, we show that for any
$\epsilon>0$, any $k=1,2,...$, and any graph $G$ and a collection $\mathcal{P}$
of $p$ vertex pairs, there exists a $(1+\epsilon)$-approximate preserver with
$O(\gamma(\epsilon,k)\cdot p+n\log k+n^{1+\frac{1}{k}})$ edges, where
$\gamma(\epsilon,k)=(\frac{\log k}{\epsilon})^{O(\log k)}$. These new
preservers are significantly sparser than the previous state-of-the-art
approximate preservers due to Kogan and Parter.
