Bellman-Ford in Almost-Linear Time for Dense Graphs
arXiv:2602.16153
Abstract
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in time by refining the shortcutting procedure introduced in Li, Li, Rao, and Zhang (2026).
21 pages