  The all-pairs shortest distances (APSD) with differential privacy (DP)
problem takes as input an undirected, weighted graph $G = (V,E, \mathbf{w})$
and outputs a private estimate of the shortest distances in $G$ between all
pairs of vertices. In this paper, we present a simple
$\widetilde{O}(n^{1/3}/\varepsilon)$-accurate algorithm to solve APSD with
$\varepsilon$-DP, which reduces to $\widetilde{O}(n^{1/4}/\varepsilon)$ in the
$(\varepsilon, \delta)$-DP setting, where $n = |V|$. Our algorithm greatly
improves upon the error of prior algorithms, namely
$\widetilde{O}(n^{2/3}/\varepsilon)$ and $\widetilde{O}(\sqrt{n}/\varepsilon)$
in the two respective settings, and is the first to be optimal up to a
polylogarithmic factor, based on a lower bound of
$\widetilde{\Omega}(n^{1/4})$.
  In the case where a multiplicative approximation is allowed, we give two
different constructions of algorithms with reduced additive error. Our first
construction allows a multiplicative approximation of $O(k\log{\log{n}})$ and
has additive error $\widetilde{O}(k\cdot n^{1/k}/\varepsilon)$ in the
$\varepsilon$-DP case and $\widetilde{O}(\sqrt{k}\cdot n^{1/(2k)}/\varepsilon)$
in the $(\varepsilon, \delta)$-DP case. Our second construction allows
multiplicative approximation $2k-1$ and has the same asymptotic additive error
as the first construction. Both constructions significantly improve upon the
currently best-known additive error of, $\widetilde{O}(k\cdot n^{1/2 +
1/(4k+2)}/\varepsilon)$ and $\widetilde{O}(k\cdot n^{1/3 +
2/(9k+3)}/\varepsilon)$, respectively. Our algorithms are straightforward and
work by decomposing a graph into a set of spanning trees, and applying a key
observation that we can privately release APSD in trees with
$O(\text{polylog}(n))$ error.
