3
[2311.02520] Single-Source Shortest Paths with Negative Real Weights in $\tilde{...
source link: https://arxiv.org/abs/2311.02520
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 4 Nov 2023 (v1), last revised 13 Nov 2023 (this version, v2)]
Single-Source Shortest Paths with Negative Real Weights in O~(mn8/9) Time
This paper presents a randomized algorithm for the problem of single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input graph with n vertices and m edges, the algorithm completes in O~(mn8/9) time with high probability. For real-weighted graphs, this result constitutes the first asymptotic improvement over the classic O(mn)-time algorithm variously attributed to Shimbel, Bellman, Ford, and Moore.
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2311.02520 [cs.DS] |
| (or arXiv:2311.02520v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2311.02520 |
Submission history
From: Jeremy Fineman [view email][v1] Sat, 4 Nov 2023 22:35:39 UTC (35 KB)
[v2] Mon, 13 Nov 2023 15:54:07 UTC (35 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK