Researchers have developed a new deterministic algorithm for single-source shortest paths (SSSP) on directed graphs that runs in O(m log^(2/3) n) time, breaking the long-standing O(m + n log n) time bound of Dijkstra's algorithm on sparse graphs. This breakthrough demonstrates that Dijkstra's algorithm is not optimal for SSSP problems and represents the first improvement to overcome the sorting barrier in this fundamental graph problem.
Sort: