An Efficient Multi-Core Parallel Implementation of SSSP Algorithm with Decreasing Delta-Stepping

Single-Source Shortest Path (SSSP) algorithms are essential in various applications, from optimizing transportation networks to analyzing social networks. This paper focuses on implementing and optimizing a parallel Delta-Stepping algorithm for SSSP on shared-memory systems. We evaluate our algorithm's performance using synthetic Kronecker graphs and large-scale real-world datasets, including LiveJournal, Orkut, and Twitter. Our parallel Delta-Stepping algorithm achieves significant speedup through several techniques: gradual reduction of the delta value, property-driven graph reordering, bucket fusion, and dynamic load balancing. Extensive experiments show that our Parallel Delta-Stepping with Decreasing Delta (PD3) achieves speedups between 10× and 65× compared to the best-known serial implementations and is faster than or comparable to other existing parallel methods. These results highlight the importance of customized parallelization strategies and algorithmic optimizations for efficient SSSP computation in shared-memory systems, with broad implications for various graph-based applications.