A Faster Directed Single-Source Shortest Path Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914317917487104 |
|---|---|
| author | Duan, Ran Mao, Xiao Shu, Xinkai Yin, Longhui |
| author_facet | Duan, Ran Mao, Xiao Shu, Xinkai Yin, Longhui |
| contents | This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07868 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Faster Directed Single-Source Shortest Path Algorithm Duan, Ran Mao, Xiao Shu, Xinkai Yin, Longhui Data Structures and Algorithms F.2.2 This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025]. |
| title | A Faster Directed Single-Source Shortest Path Algorithm |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2602.07868 |