Bellman-Ford in Almost-Linear Time for Dense Graphs

George Z. Li, Jason Li, Junkai Zhang

We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $n^{2+o(1)}$ time by refining t…