Faster single-source shortest paths with negative real weights via proper hop distance
<|reference_start|>Faster single-source shortest paths with negative real weights via proper hop distance: The textbook algorithm for single-source shortest paths with real-valued edge weights runs in $O(m n)$ time on a graph with $m$ edges and $n$ vertices. A recent breakthrough algorithm by Fineman [Fin24] takes $\tilde O(m n^{8/9})$ randomized time. We present an $\tilde O(m n^{4/5})$ randomized time algorithm building on ideas from [Fin24].<|reference_end|>
@article{huang2024faster,
    title={Faster single-source shortest paths with negative real weights via
  proper hop distance},
    author={Yufan Huang, Peter Jin, Kent Quanrud},
    journal={arXiv preprint arXiv:2407.04872},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04872},
    primaryClass={cs.DS}
}