# Faster single-source shortest paths with negative real weights via proper hop distance

Preprint · Yufan Huang, Peter Jin, Kent Quanrud

- Archive id: arxiv:2407.04872
- Published: 2024-07-05
- arXiv: https://arxiv.org/abs/2407.04872
- Source URL: https://arxiv.org/abs/2407.04872
- PDF: https://arxiv.org/pdf/2407.04872
- Provenance: arxiv

## Abstract

The textbook algorithm for single-source shortest paths with real-valued edge weights runs in $O(m n)$ time on a graph with $m$ edges and $n$ vertices. A recent breakthrough algorithm by Fineman \[Fin24\] takes $\\tilde O(m n^{8/9})$ randomized time. We present an $\\tilde O(m n^{4/5})$ randomized time algorithm building on ideas from \[Fin24\].

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