  We revisit the problem of privately releasing the all-pairs shortest path
distances of a weighted undirected graph up to low additive error, which was
first studied by Sealfon [Sea16]. In this paper, we improve significantly on
Sealfon's results, both for arbitrary weighted graphs and for bounded-weight
graphs on $n$ nodes. Specifically, we provide an approximate-DP algorithm that
outputs all-pairs shortest path distances up to maximum additive error
$\tilde{O}(\sqrt{n})$, and a pure-DP algorithm that outputs all pairs shortest
path distances up to maximum additive error $\tilde{O}(n^{2/3})$ (where we
ignore dependencies on $\varepsilon, \delta$). This improves over the previous
best result of $\tilde{O}(n)$ additive error for both approximate-DP and
pure-DP [Sea16], and partially resolves an open question posed by Sealfon
[Sea16, Sea20]. We also show that if the graph is promised to have reasonably
bounded weights, one can improve the error further to roughly
$n^{\sqrt{2}-1+o(1)}$ in the approximate-DP setting and roughly
$n^{(\sqrt{17}-3)/2 + o(1)}$ in the pure-DP setting. Previously, it was only
known how to obtain $\tilde{O}(n^{1/2})$ additive error in the approximate-DP
setting and $\tilde{O}(n^{2/3})$ additive error in the pure-DP setting for
bounded-weight graphs [Sea16].
