TY - GEN
T1 - Adaptive Optimizations for Parallel Single-Source Shortest Paths
AU - Hu, Runbang
AU - Li, Chaoqun
AU - Du, Xiaojiang
AU - Ji, Yuede
N1 - Publisher Copyright:
© 2025 Copyright is held by the owner/author(s).
PY - 2025/5/2
Y1 - 2025/5/2
N2 - The single-source shortest path (SSSP) problem is essential in graph theory with applications in navigation, biology, social networks, and traffic analysis. The Δ-Stepping algorithm enhances parallelism by grouping vertices into "buckets"based on their tentative distances. However, its performance depends on Δvalues and graph properties. This paper introduces an adaptive parallel Δ-Stepping implementation with three innovations: neighbor reordering, bucket fusion, and graph type-aware Δselection. Tested on 11 diverse graphs, it achieves an average 7.1× speedup over serial Dijkstra's algorithm on a 48-threads CPU.
AB - The single-source shortest path (SSSP) problem is essential in graph theory with applications in navigation, biology, social networks, and traffic analysis. The Δ-Stepping algorithm enhances parallelism by grouping vertices into "buckets"based on their tentative distances. However, its performance depends on Δvalues and graph properties. This paper introduces an adaptive parallel Δ-Stepping implementation with three innovations: neighbor reordering, bucket fusion, and graph type-aware Δselection. Tested on 11 diverse graphs, it achieves an average 7.1× speedup over serial Dijkstra's algorithm on a 48-threads CPU.
UR - https://www.scopus.com/pages/publications/105008291155
UR - https://www.scopus.com/pages/publications/105008291155#tab=citedBy
U2 - 10.1145/3711708.3723450
DO - 10.1145/3711708.3723450
M3 - Conference contribution
AN - SCOPUS:105008291155
T3 - Proceedings of the 1st FastCode Programming Challenge, FCPC 2025
SP - 53
EP - 56
BT - Proceedings of the 1st FastCode Programming Challenge, FCPC 2025
T2 - 1st FastCode Programming Challenge, FCPC 2025
Y2 - 1 March 2025 through 5 March 2025
ER -