  In this paper we show a deterministic parallel all-pairs shortest paths
algorithm for real-weighted directed graphs. The algorithm has
$\tilde{O}(nm+(n/d)^3)$ work and $\tilde{O}(d)$ depth for any depth parameter
$d\in [1,n]$. To the best of our knowledge, such a trade-off has only been
previously described for the real-weighted single-source shortest paths problem
using randomization [Bringmann et al., ICALP'17]. Moreover, our result improves
upon the parallelism of the state-of-the-art randomized parallel algorithm for
computing transitive closure, which has $\tilde{O}(nm+n^3/d^2)$ work and
$\tilde{O}(d)$ depth [Ullman and Yannakakis, SIAM J. Comput. '91]. Our APSP
algorithm turns out to be a powerful tool for designing efficient planar graph
algorithms in both parallel and sequential regimes.
  One notable ingredient of our parallel APSP algorithm is a simple
deterministic $\tilde{O}(nm)$-work $\tilde{O}(d)$-depth procedure for computing
$\tilde{O}(n/d)$-size hitting sets of shortest $d$-hop paths between all pairs
of vertices of a real-weighted digraph. Such hitting sets have also been called
$d$-hub sets. Hub sets have previously proved especially useful in designing
parallel or dynamic shortest paths algorithms and are typically obtained via
random sampling. Our procedure implies, for example, an $\tilde{O}(nm)$-time
deterministic algorithm for finding a shortest negative cycle of a
real-weighted digraph. Such a near-optimal bound for this problem has been so
far only achieved using a randomized algorithm [Orlin et al., Discret. Appl.
Math. '18].
