Bellman-Ford in Almost-Linear Time

2026/07/21 by Isaac M. Hair, George Z. Li, Jason Li +1 · 1 voice
#cs.DS

paper · pdf

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.

Citations

• Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
• Negative-Weight Single-Source Shortest Paths in Near-linear Time
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Discussions

• 3 recent major breakthroughs in algorithms and data structures: 1. Shortest path in almost linear time even for real negative weights arxiv.org/abs/2607.19346 [bsky, 20 points, 1 comments]

Related

• Bellman-Ford is optimal for shortest hop-bounded paths
• Single-Source Shortest Paths with Negative Real Weights in O(mn^8/9) Time
• Negative-Weight Single-Source Shortest Paths in Near-linear Time
• Breaking the Bellman-Ford Shortest-Path Bound
• Lower Bounds for Non-Adaptive Shortest Path Relaxation