# Breaking the Bellman-Ford Shortest-Path Bound

Preprint · Amr Elmasry

- Archive id: arxiv:1905.01325
- Published: 2019-05-03
- arXiv: https://arxiv.org/abs/1905.01325
- Source URL: https://arxiv.org/abs/1905.01325
- PDF: https://arxiv.org/pdf/1905.01325
- Provenance: arxiv

## Abstract

In this paper we give a single-source shortest-path algorithm that breaks, after over 60 years, the $O(n \\cdot m)$ time bound for the Bellman-Ford 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(\\sqrt{n},\\sqrt{m/\\log n})$ calls to Dijkstra's algorithm, such that the shortest-path tree is the same for the new graph as that 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})$. We also give a second implementation that performs few calls to Dijkstra's algorithm if the graph contains few negative arcs on the shortest-path tree.

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