# Single-Source Shortest Paths with Negative Real Weights in $\tilde{O}(mn^{8/9})$ Time

Preprint · Jeremy T. Fineman

- Archive id: arxiv:2311.02520
- Published: 2023-11-04
- arXiv: https://arxiv.org/abs/2311.02520
- Source URL: https://arxiv.org/abs/2311.02520
- PDF: https://arxiv.org/pdf/2311.02520
- Provenance: arxiv

## Abstract

This paper presents a randomized algorithm for the problem of single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input graph with $n$ vertices and $m$ edges, the algorithm completes in $\\tilde{O}(mn^{8/9})$ time with high probability. For real-weighted graphs, this result constitutes the first asymptotic improvement over the classic $O(mn)$-time algorithm variously attributed to Shimbel, Bellman, Ford, and Moore.

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