Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
arxiv.org/pdf/2504.17033This is the first result to break the O(m+ n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.