分享一篇论文
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
https://arxiv.org/abs/2504.17033
Abstract:
We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.
Wow，没想到 Dijkstra's shortest path 还能被突破，虽然我看不懂论文但是好厉害
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
https://arxiv.org/abs/2504.17033
Abstract:
We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.
Wow，没想到 Dijkstra's shortest path 还能被突破，虽然我看不懂论文但是好厉害