# A Faster Directed Single-Source Shortest Path Algorithm

Preprint · Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin

- Archive id: arxiv:2602.07868
- Published: 2026-02-08
- arXiv: https://arxiv.org/abs/2602.07868
- Source URL: https://arxiv.org/abs/2602.07868
- PDF: https://arxiv.org/pdf/2602.07868
- Provenance: arxiv

## Abstract

This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\\sqrt{\\log n}+\\sqrt{mn\\log n\\log \\log n})$, which is $O(m\\sqrt{\\log n\\log \\log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\\log^{2/3} n)$ time for directed SSSP algorithm \[Duan, Mao, Mao, Shu, Yin 2025\].

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