# Bellman-Ford in Almost-Linear Time

Preprint · Isaac M. Hair, George Z. Li, Jason Li, Junkai Zhang

- Archive id: arxiv:2607.19346
- Published: 2026-07-21
- arXiv: https://arxiv.org/abs/2607.19346
- Citations: 0
- Source URL: https://arxiv.org/abs/2607.19346
- PDF: https://arxiv.org/pdf/2607.19346
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

Cited in dossiers:
- [Algorithms & Complexity Breakthroughs: State of the Field (October 2026)](https://space-kitty.com/dossiers/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.