Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913965530939392 |
|---|---|
| author | Duan, Ran Mao, Jiayi Mao, Xiao Shu, Xinkai Yin, Longhui |
| author_facet | Duan, Ran Mao, Jiayi Mao, Xiao Shu, Xinkai Yin, Longhui |
| contents | We give a deterministic $O(m\log^{2/3}n)$-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the $O(m+n\log n)$ time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17033 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Breaking the Sorting Barrier for Directed Single-Source Shortest Paths Duan, Ran Mao, Jiayi Mao, Xiao Shu, Xinkai Yin, Longhui Data Structures and Algorithms F.2.2 We give a deterministic $O(m\log^{2/3}n)$-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the $O(m+n\log n)$ time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP. |
| title | Breaking the Sorting Barrier for Directed Single-Source Shortest Paths |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2504.17033 |