The single-source shortest path (SSSP) problem is a fundamental problem in graph theory with applications in navigation [26,28], social network analysis [5,9,13,17,18,24], traffic analysis [25], cybersecurity applications [6,12,15,16], and computing other graph algorithms [10].
Dijkstra's algorithm is a classic algorithm for finding SSSP on non-negative weighted regular graphs, while its sequential priority queue operations limit parallelism [7,14,29]. To address that, the -Stepping algorithm groups vertices into "buckets" based on tentative distances, enabling parallel processing. However, its performance depends on values and graph properties, such as diameter, weight distribution, and sparsity. While previous optimizations exist for specific graphs [3,8], an adaptive approach remains an open challenge [22,31]. This paper presents an adaptive parallel -Stepping implementation that integrates graph-specific preprocessing and dynamic strategy selection. There are three key innovations. (i) Neighbor reordering reorganizes edges based on their weights and classifies graphs by properties such as diameter and density to improve selection. (ii) Bucket fusion reduces synchronization overhead by combining consecutive processing rounds for the same bucket. It will relax the current bucket repeatedly until no new insertions occur. (iii) Adaptively optimizations adaptively switches between standard -Stepping, and bucket fusion. This can optimize the trade-off between parallelism and synchronization.
We evaluated our method on 11 diverse graphs, achieving an average 7.1⇥ speedup over serial Dijkstra's algorithm on a 48-thread system, with more than 12⇥ speedup for dense, and small-diameter graphs.
To improve the performance of serial SSSP implementations, parallel approaches have been proposed, such as Bellman-Ford [11] and -Stepping [27].
-Stepping improves efficiency by reducing redundant computations in parallel Bellman-Ford while balancing parallelism and synchronization overhead. It groups vertices into buckets based on their tentative distances and processes them in two stages: first relaxing light edges ( ) in parallel, followed by handling heavy edges (> ). This design maximizes concurrency for small-weight edges while minimizing excessive fragmentation and synchronization, making -Stepping highly effective for favorable graph structures.
Selection of value. The bucket size directly impacts performance. A small increases parallelism but raises synchronization costs, while a large reduces synchronization but may over-group vertices, limiting efficiency. Finding the optimal across different graph types remains challenging.
Workload imbalance is another challenge in parallel SSSP algorithms. Sparse graphs may lead to underutilization of resources due to mostly empty buckets, while dense graphs with uniform edge weights require careful dependency management to prevent bottlenecks. Existing solutions, such as bucket fusion (which consolidates adjacent buckets to reduce synchronization) and dynamic tuning, help mitigate these issues. However, these techniques often require manual tuning and are not universally effective across all graph types.
Our method is based on -Stepping algorithm by creating parallel regions to reduce repeated thread allocation overhead. First, we implement a hybrid bucket architecture combining thread-local storage with synchronized global coordination, where each thread independently manages its bucket for tentative distance updates, minimizing communication between threads during light edge relaxation. After processing the light edges, each thread handles heavy edges once. Periodically, the threads atomically commit their local minimum bucket index to a shared global bucket, consolidating related vertices, and processing them in parallel. In addition, we apply three optimizations as discussed below, including neighbor reordering, bucket fusion, and adaptive optimizations.
Neighbor Reordering. The -Stepping algorithm requires separating light and heavy edges, which can be done in three ways: (i) scanning edges at runtime, (ii) using a status array of size |⇢| to mark edge types, (iii) maintaining separate queues for light and heavy edges. However, these approaches have drawbacks: redundant computation (i, ii), extra memory usage (ii, iii), and poor cache utilization (iii). To address these issues, we introduce neighbor reordering. Particularly, we reorder each vertex's adjacency list in ascending weight order and use an additional offset array with the size of |+ | (> Bucket Fusion. A single bucket often requires multiple processing rounds to relax the bucket, updating tentative distances, and reinserting vertices until no new insertions occur. This repeated reprocessing introduces significant overhead. To mitigate this, we apply bucket fusion, which combines consecutive processing rounds within the same bucket. By allowing threads to continue execution without frequent global barriers, this technique substantially lowers synchronization costs. We introduce a threshold-based approach (e.g., 1,000 vertices) to optimize workload distribution: If a bucket has a small workload, the owning thread processes it immediately. Otherwise, it is passed to a global bucket for shared processing. This strategy prevents straggler overload and ensures efficient workload balancing.
Adaptive Optimizations. Real-world graphs vary widely in structure, including sparse vs. dense, real vs. uniform weights, and small vs. large diameters. To optimize -Stepping across different graphs, we introduce adaptive strategies.
value is crucial for balancing parallelism and redundant computation in the -Stepping algorithm. It determines the granularity of buckets, influencing synchronization costs and workload distribution. We define as: = (<0G_F486⌘C Small graphs are special as the dominant cost may shift from computation to thread management and synchronization overhead, making multi-threading less efficient than a serial approach. In such cases, we switch to serial -Stepping with a small value to optimize performance. A graph is classified as small if its Compressed Sparse Row (CSR) [4] representation fits within the L1 cache, ensuring efficient memory access. CSR is a graph representation that is widely used in graph analytics [10,[19][20][21]23]. Given a 32 KB L1 cache, and assuming Unsigned integer for the begin position and adjacency list arrays, and Single-precision floating point for edge weights, this condition is expressed as
Table 1 summarizes the details of the tested graph benchmark. We evaluate our method on the graph benchmarks and compare against a baseline algorithm, i.e., the priority queuebased Dijkstra's algorithm. We use a CPU instance with 48 threads and 96 GB memory on the Speedcode platform [30].
Table 2 summarizes the results. (i) On average, our method achieves 7.1⇥ speedup over the Dijkstra's algorithm, which is a significant improvement. (ii) For most graphs, our parallel -Stepping algorithm significantly outperforms the Dijkstra's algorithm. (iii) Our method underperforms on three graphs (CN, SN, and KG), which illustrates that parallelism does not always guarantee performance gains. Additionally, the lack of a clear boundary between graph categories can occasionally lead to suboptimal strategy selection.
Neighbor reordering. Figure 1 shows the performance in terms of million edges per second with and without neighbor reordering. We have two interesting observations. (i) On average, neighbor reordering can improve the performance by 1.4⇥ speedup on all the graphs, showing a stable performance improvement. (ii) Neighbor reordering achieves the highest speedup for WG and SD graphs, which are 2.3⇥, 2.4⇥, respectively. This clearly shows the benefits of neighbor reordering.
Bucket fusion. Figure 2 shows the performance of Dijkstra's algorithm, original (without bucket fusion), and with bucket fusion. We show the performance for three representative graphs, including a sparse graph (SN), a dense graph (KG), and an extremely dense graph (CN). We observe that it has varying effects based on graph properties. In sparse graphs (e.g., SN), it lowers synchronization overhead and improves performance. However, in dense graphs (e.g., KG), fusion causes workload imbalance, as profiling shows a single thread often dominates fusion operations, leaving others idle. This workload imbalance arises from non-uniform bucket sizes, where frequent fusion is unevenly distributed. Small graph. Figure 3 shows the performance on small graphs. The serial -Stepping algorithm demonstrates superior performance, as the overhead associated with thread management in parallel -Stepping outweighs its parallelization benefits. When the number of vertices is less than 2K, serial -Stepping achieves a 1.5 2⇥ speedup over the parallel implementation. However, as the graph size increases, the parallel algorithm gradually surpasses the serial version, while the efficiency of the serial approach declines, eventually converging to the performance of Dijkstra's algorithm. When the graph reaches 10K vertices, the parallel method achieves a 1.7⇥ speedup over the serial approach.
Improvements of -Stepping [27] have focused on tuning to graph properties and optimizing buckets [32] (e.g., fusion and priority-aware splitting) to reduce synchronization overhead. While merging underpopulated buckets improves performance in road networks, it can cause load imbalance in dense graphs [1,2,33]. Preprocessing, such as edge sorting, helps reduce redundant relaxations but often relies on static heuristics that overlook graph heterogeneity.
This paper presents an adaptive parallel -Stepping implementation that integrates three key innovations, including neighbor reordering, bucket fusion, and adaptive optimization. We test our method on 11 diverse graphs in terms of size, diameter, density, and edge weight variance. On a CPU server with 48 threads, our method achieves an average of 7.1⇥ speedup over the serial Dijkstra's algorithm.