Bellman-Ford in Almost-Linear Time for Dense Graphs
George Z. Li, Jason Li, Junkai Zhang · 2026
Read Bellman-Ford in Almost-Linear Time for Dense Graphs by George Z. Li, Jason Li, Junkai Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-16153.txt.
Description
George Li, Jason Li, and Junkai Zhang solve the single-source shortest paths problem on directed graphs with real-valued edge weights, which may be negative. Their paper refines the shortcutting procedure introduced by Li, Li, Rao, and Zhang in an earlier work, pushing the running time down to just above quadratic in the number of vertices. The abstract states the result crisply, with the refinement itself as the contribution.
For readers in algorithms, the interest lies in that tight bound for a classic problem where negative weights rule out the simplest methods. A near-quadratic algorithm for directed graphs with arbitrary real weights narrows the gap between what is known to be possible and the quadratic barrier that dense graphs suggest. The paper thus offers a cleaner, faster route to shortest paths in a setting where edge weights can pull in both directions.
Catalog record
| CREATOR | George Z. Li, Jason Li, Junkai Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-16153