  We study the problem of releasing the weights of all-pair shortest paths in a
weighted undirected graph with differential privacy (DP). In this setting, the
underlying graph is fixed and two graphs are neighbors if their edge weights
differ by at most $1$ in the $\ell_1$-distance. We give an $\epsilon$-DP
algorithm with additive error $\tilde{O}(n^{2/3} / \epsilon)$ and an
$(\epsilon, \delta)$-DP algorithm with additive error $\tilde{O}(\sqrt{n} /
\epsilon)$ where $n$ denotes the number of vertices. This positively answers a
question of Sealfon (PODS'16), who asked whether a $o(n)$-error algorithm
exists. We also show that an additive error of $\Omega(n^{1/6})$ is necessary
for any sufficiently small $\epsilon, \delta > 0$.
  Finally, we consider a relaxed setting where a multiplicative approximation
is allowed. We show that, with a multiplicative approximation factor $k$, %$2k
- 1$, the additive error can be reduced to $\tilde{O}\left(n^{1/2 + O(1/k)} /
\epsilon\right)$ in the $\epsilon$-DP case and $\tilde{O}(n^{1/3 + O(1/k)} /
\epsilon)$ in the $(\epsilon, \delta)$-DP case, respectively.
