There is a new sorting algorithm a deterministic O(m log2/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 the first result to break the O(m + n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.
This improves on Turing award winner Tarjan’s O(m + nlogn) with Dijkstra’s, something every Computer Science student learns in college.
It combines techniques from Bellman-Ford, a slower algorithm and Dijkstra’s to improve runtime. It minimizies reliance on priority queue sorting by processing multiple nodes (the “frontier”) at once using new data structures, conquering the sorting bottleneck especially on sparse graphs.
Quantitative Improvement
Old Bound (Dijkstra): O(m+nlogn)O(m+nlogn)
New Bound: O(mlog2/3n)O(mlog2/3n)
For sparse graphs where mm is about O(n)O(n), this is asymptotically faster as nn grows.
Practical & Theoretical Impact
Theoretical:
Shifts understanding of shortest-path computation for directed graphs.
Inspires new research avenues for optimal graph algorithms free from sorting constraints.
Provides evidence that further improvements may be possible.
Practical:
Faster algorithms for huge, sparse networks (transportation, routing, social networks).
Scalability: Networks with millions of nodes/edges can see noticeable speed gains.
Techniques may generalize or inspire improvements for more complex scenarios (e.g., weighted, negative edges, dynamic graphs).
Hybrid models (using Bellman-Ford for initialization and Dijkstra for steady-state, or other combinations) have shown improved adaptability, robustness, and computational efficiencies, especially when combined with machine learning for real-time route selection.
It challenges assumptions about comparison-based bounds, potentially influencing related problems like all-pairs shortest paths or dynamic graph algorithms. Discussions highlight its unusual log2/3n\log^{2/3} n\log^{2/3} n factor as a novel recursive partitioning trick. It could inspire other improvements to sorting.
Applications:
Navigation and Routing: Faster GPS recalculations, traffic simulation, and logistics (e.g., cheaper deliveries via optimized paths).
Networks and Graphs: Quicker routing in computer networks, social graphs, or biological pathways.
Potential in AI/ML: Could accelerate graph-based models (e.g., in recommendation systems or reinforcement learning pathfinding).
There is high implementation complexity and possible large constants. It is slower than tuned Dijkstra variants (e.g., with binary heaps) or heuristics like A* and contraction hierarchies in road networks.
This will be refined and improved.
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.
This is good and it’s nice to add to the tool kit but in practice it was almost always better to use the easiect alogorithm possilbe and measure the performance in practice on real data sets before going hog wild with the bleeding edge alogorithms. I learned this early in my career when my lead had me implement an optimized version of an alogorithm and it turned out that it made no difference in the performance. Unless you are super familiar with something (like I was was with instruction scheduling fow VLIW processors) trying to optimize things is a waste of time
And that’s why all our software is bloatware, folks. Just wasn’t worth his time because compute became cheap by the year 2005.
I hope when we wind up using more electricity on AI compute then we use on lighting, people try to improve the software instead of brute forcing the easiest algorithm possible.
I myself often brute force an answer, but I’m not formally trained in programming..
It depends on the application.
If you’re sorting records once a week, it’s irrelevant.
If you need to sort through 2 billion packets per second in a high-trhoughput switch, every cycle counts.