Bellman-Ford in Almost-Linear Time
2026-07-21 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to find the shortest paths from one starting point to all other points in a directed graph where the connections between points can have both positive and negative values. They present a method that solves this problem very quickly, with a running time close to linear in the number of connections. This improves our understanding of how efficiently shortest paths can be computed even with tricky edge weights.
single-source shortest pathsdirected graphnegative edge weightsreal-valued weightsgraph algorithmstime complexityshortest path problemalgorithm efficiency
Authors
Isaac M. Hair, George Z. Li, Jason Li, Junkai Zhang
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 $m^{1+o(1)}$ time.