The shortest path problem is one of the central problems in distributed computing. For the last few years, substantial progress has been made on the \textit{approximate} single source shortest paths problem [Nan14, HKN16, EN16, BKKL16], culminating in an $\tilde O(D+\sqrt n)$ algorithm to compute $(1+o(1))$-approximate shortest paths, where $D$ is the diameter of the graph. Up to polylogarithmic factors, this running time matches the lower bound of [PR99].
The question of exact shortest paths in distributed computing, however, was unresolved for over a decade, until the recent breakthrough of [Elk17] established a sublinear-time algorithm for exact single source shortest paths on undirected graphs. Shortly after, [HNS17] considered the exact all pairs shortest paths problem on directed graphs.
In this paper, we show the first sublinear time single source shortest path algorithm for directed graphs, running in $\tilde O(n^{3/4}D^{1/4})$ time. For small values of $D$, this algorithm improves the $\tilde O(n^{5/6})$ time algorithm of [Elk17] and also works for directed graphs. Our algorithm extends to the exact $s$ sources shortest path problem, in which we provide the fastest algorithms for reasonably small $s$ and $D$.