Researchers have developed a new deterministic shortest path algorithm with O(m log^(2/3) n) time complexity that outperforms Dijkstra's O(m + n log n) bound on sparse graphs. The algorithm combines techniques from Bellman-Ford and Dijkstra, processing multiple nodes simultaneously to reduce reliance on priority queue sorting. While theoretically significant as the first improvement over Dijkstra for single-source shortest paths, practical applications may be limited by implementation complexity and large constants, though it shows promise for large sparse networks in navigation, routing, and AI applications.

Sort: