# A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths

Preprint · Sunny Atalig, Marek Chrobak

- Archive id: arxiv:2508.04872
- Published: 2025-08-06
- arXiv: https://arxiv.org/abs/2508.04872
- Source URL: https://arxiv.org/abs/2508.04872
- PDF: https://arxiv.org/pdf/2508.04872
- Provenance: arxiv

## Abstract

In this note we examine the recent paper "Breaking the Bellman-Ford Shortest-Path Bound" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem and claims that its running time complexity is $\\tilde{O}(m\\sqrt{n})$, where $n$ is the number of vertices and $m$ is the number of edges. We show that his analysis is incorrect, by providing an example of a weighted graph on which the running time of his algorithm is $Ω(mn)$.

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