# Breaking the Bellman-Ford Shortest-Path Bound

Preprint · Amr Elmasry

- Archive id: arxiv:2410.23383
- Published: 2024-10-30
- arXiv: https://arxiv.org/abs/2410.23383
- Source URL: https://arxiv.org/abs/2410.23383
- PDF: https://arxiv.org/pdf/2410.23383
- Provenance: arxiv

## Abstract

In this paper we give a single-source shortest-path algorithm that breaks, after over 65 years, the $O(n \\cdot m)$ bound for the running time of the Bellman-Ford-Moore algorithm, where $n$ is the number of vertices and $m$ is the number of arcs of the graph. Our algorithm converts the input graph to a graph with nonnegative weights by performing at most $\\min(2 \\cdot \\sqrt{n},2 \\cdot \\sqrt{m/\\log n})$ calls to a modified version of Dijkstra's algorithm, such that the shortest-path trees are the same for the new graph as those for the original. When Dijkstra's algorithm is implemented using Fibonacci heaps, the running time of our algorithm is therefore $O(\\sqrt{n} \\cdot m + n \\cdot \\sqrt{m \\log n})$.

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

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