Problem & significance.
Single-source shortest paths (SSSP) on directed graphs with non-negative real weights is a pillar of graph algorithms. For decades, the textbook gold standard has been Dijkstra’s algorithm with good heaps, running in the comparison-addition model (only comparisons and additions on weights).… Read More
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
