New algorithm finds the shortest path to any point in record time
5mon 28d ago by piefed.zip/u/Ludicrous0251 in theydidthemath@mander.xyz from www.earth.com
A new technique breaks Dijkstra's 70-year-old record: it finds routes faster in huge networks, changing graph theory forever.
https://arxiv.org/abs/2504.17033
We give a deterministic 
-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 
time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.