Post #12291 190 May 28, 2025, 14:29 UTC New algorithm beats Dijkstra's time for shortest paths in directed graphshttps://arxiv.org/abs/2504.17033https://redd.it/1kxedmp@programmingreddit arXiv.org Breaking the Sorting Barrier for Directed Single-Source Shortest Paths We give a deterministic $O(m\log^{2/3}n)$-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is...