# Shortcutting for Negative-Weight Shortest Path

Preprint · George Z. Li, Jason Li, Satish Rao, Junkai Zhang

- Archive id: arxiv:2511.12714
- Published: 2025-11-16
- arXiv: https://arxiv.org/abs/2511.12714
- Citations: 0
- Source URL: https://arxiv.org/abs/2511.12714
- PDF: https://arxiv.org/pdf/2511.12714
- Provenance: arxiv

## Abstract

Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in $O(n^{2.5}\\log^{4.5}n)$ time, improving on prior work of Fineman (STOC 2024) and Huang-Jin-Quanrud (SODA 2025, 2026) on dense graphs. Our main technique is an shortcutting procedure that iteratively reduces the number of negative-weight edges along shortest paths by a constant factor.

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/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.