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

Sunny Atalig, Marek Chrobak

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…