We present an experimental study of the single source shortest path problem with non-negative edge weights (NSSP) on largescale
graphs using the Delta-stepping parallel algorithm. We report performance results on the Cray MTA-2, a multithreaded
parallel computer. The MTA-2 is a high-end shared memory system offering two unique features that aid the efficient parallel
implementation of irregular algorithms: the ability to exploit fine-grained parallelism, and low-overhead synchronization primitives.
Our implementation exhibits remarkable parallel speedup when compared with competitive sequential algorithms, for
low-diameter sparse graphs. For instance, Delta-stepping on a directed scale-free graph of 100 million vertices and 1 billion edges
takes less than ten seconds on 40 processors of the MTA-2, with a relative speedup of close to 30. To our knowledge, these
are the first performance results of a shortest path problem on realistic graph instances in the order of billions of vertices and