  We consider differentially private range queries on a graph where query
ranges are defined as the set of edges on a shortest path of the graph. Edges
in the graph carry sensitive attributes and the goal is to report the sum of
these attributes on a shortest path for counting query or the minimum of the
attributes in a bottleneck query. We use differential privacy to ensure that
the release of these query answers provide protection of the privacy of the
sensitive edge attributes. Our goal is to develop mechanisms that minimize the
additive error of the reported answers with the given privacy budget. In this
paper we report non-trivial results for private range queries on shortest
paths. For counting range queries we can achieve an additive error of $\tilde
O(n^{1/3})$ for $\varepsilon$-DP and $\tilde O(n^{1/4})$ for $(\varepsilon,
\delta)$-DP. We present two algorithms where we control the final error by
carefully balancing perturbation added to the edge attributes directly versus
perturbation added to a subset of range query answers (which can be used for
other range queries). Bottleneck range queries are easier and can be answered
with polylogarithmic additive errors using standard techniques.
