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 O(m n8/9) randomized time. We present an O(m n4/5) randomized time algorithm building on ideas from [Fin24].
No takes yet. Share an insight, caveat, or question.
Huang et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: