Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912901527240704 |
|---|---|
| author | Castro, Lucas Clementino, Thailsson de Freitas, Rosiane |
| author_facet | Castro, Lucas Clementino, Thailsson de Freitas, Rosiane |
| contents | We present an implementation and experimental analysis of the deterministic algorithm proposed by Duan et al. (2025) for the Single-Source Shortest Path (SSSP) problem, which achieves the best-known asymptotic upper bound of $O(m \log^{2/3} n)$. We provide a worst-case C++ implementation of this algorithm utilizing $O(n \log^{1/3} n)$ space, as well as a variant that reduces memory usage to $O(n)$ while maintaining the same time complexity in expectation. We compare these implementations against Dijkstra's algorithm on sparse random graphs, grids, and U.S. road networks with up to 10 million vertices. Our results show that while the implementations adhere to their theoretical complexity bounds, large constant factors hinder their practical utility; Dijkstra's algorithm remains 3 to 4 times faster in all tested scenarios. Furthermore, we estimate that the number of vertices would need to vastly exceed $10^{67}$ for the worst-case implementation to outperform Dijkstra's. These findings suggest that a substantial reduction in constant factors is required before this theoretical breakthrough can displace established methods in practical applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03007 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths Castro, Lucas Clementino, Thailsson de Freitas, Rosiane Data Structures and Algorithms We present an implementation and experimental analysis of the deterministic algorithm proposed by Duan et al. (2025) for the Single-Source Shortest Path (SSSP) problem, which achieves the best-known asymptotic upper bound of $O(m \log^{2/3} n)$. We provide a worst-case C++ implementation of this algorithm utilizing $O(n \log^{1/3} n)$ space, as well as a variant that reduces memory usage to $O(n)$ while maintaining the same time complexity in expectation. We compare these implementations against Dijkstra's algorithm on sparse random graphs, grids, and U.S. road networks with up to 10 million vertices. Our results show that while the implementations adhere to their theoretical complexity bounds, large constant factors hinder their practical utility; Dijkstra's algorithm remains 3 to 4 times faster in all tested scenarios. Furthermore, we estimate that the number of vertices would need to vastly exceed $10^{67}$ for the worst-case implementation to outperform Dijkstra's. These findings suggest that a substantial reduction in constant factors is required before this theoretical breakthrough can displace established methods in practical applications. |
| title | Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.03007 |