  The single-source shortest path (SSSP) problem is a well-studied problem that
is used in many applications. In the parallel setting, a work-efficient
algorithm that additionally attains $o(n)$ parallel depth has been elusive.
Alternatively, various approaches have been developed that take advantage of
specific properties of a particular class of graphs. On a graphics processing
unit (GPU), the current state-of-the-art SSSP algorithms are implementations of
the Delta-stepping algorithm, which does not perform well for graphs with large
diameters. The main contribution of this work is to provide an algorithm
designed for GPUs that runs efficiently for such graphs.
  We present the parallel bucket heap, a parallel cache-efficient data
structure adapted for modern GPU architectures that supports standard priority
queue operations, as well as bulk update. We analyze the structure in several
well-known computational models and show that it provides both optimal
parallelism and is cache-efficient. We implement the parallel bucket heap and
use it in a parallel variant of Dijkstra's algorithm to solve the SSSP problem.
Experimental results indicate that, for sufficiently large, dense graphs with
high diameter, we outperform the current state-of-the-art SSSP implementations
on an NVIDIA RTX 2080 Ti and Quadro M4000 by up to a factor of 2.8 and 5.4,
respectively.
