Overview

• NextBigFuture blogger Brian Wang reported on August 14 that an unnamed research group has devised a deterministic O(m log²/³ n) single-source shortest-path algorithm for directed graphs with non-negative weights, marking the first claim to outpace the classical O(m + n log n) Dijkstra bound on sparse networks.
• South China Morning Post identifies the work as coming from Duan Ran’s team at Tsinghua University, noting its publication as an arXiv preprint and its receipt of a Best Paper Award at the June STOC conference despite lacking formal peer review.
• The method fuses Bellman–Ford initialization with Dijkstra-like relaxation and replaces per-node priority-queue sorting by processing multiple frontier nodes via a recursive partitioning strategy that yields the log²/³ n improvement.
• The reported asymptotic advantage could reshape theoretical understanding of sorting-avoidant graph algorithms and promise scalability gains for massive sparse graphs, though high implementation complexity and large constant factors may limit practical speedups.
• Broader acceptance depends on independent proof verification and empirical benchmarks to evaluate hidden constants, coding feasibility, and comparative performance against tuned Dijkstra variants and heuristic routing methods.