  The hereditary discrepancy of a set system is a certain quantitative measure
of the pseudorandom properties of the system. Roughly, hereditary discrepancy
measures how well one can $2$-color the elements of the system so that each set
contains approximately the same number of elements of each color. Hereditary
discrepancy has well-studied applications e.g. in communication complexity and
derandomization. More recently, the hereditary discrepancy of set systems of
shortest paths has found applications in differential privacy [Chen et al.~SODA
23].
  The contribution of this paper is to improve the upper and lower bounds on
the hereditary discrepancy of set systems of unique shortest paths in graphs.
In particular, we show that any system of unique shortest paths in an
undirected weighted graph has hereditary discrepancy $\widetilde{O}(n^{1/4})$,
and we construct lower bound examples demonstrating that this bound is tight up
to hidden $\text{polylog } n$ factors. Our lower bounds apply even in the
planar and bipartite settings, and they improve on a previous lower bound of
$\Omega(n^{1/6})$ obtained by applying the trace bound of Chazelle and Lvov
[SoCG'00] to a classical point-line system of Erd\H{o}s.
  As applications, we improve the lower bound on the additive error for
differentially-private all pairs shortest distances from $\Omega(n^{1/6})$
[Chen et al.~SODA 23] to $\Omega(n^{1/4})$, and we improve the lower bound on
additive error for the differentially-private all sets range queries problem to
$\Omega(n^{1/4})$, which is tight up to hidden $\text{polylog } n$ factors
[Deng et al.~WADS 23].
