Breaking the sorting barrier for directed single-source shortest paths
18 days ago
- #computer science
- #shortest path
- #algorithm
- A new algorithm breaks the 'sorting barrier' in finding the shortest paths in networks, surpassing Dijkstra's algorithm.
- The shortest-paths problem involves finding the most efficient route from a starting point to all other points in a network.
- Dijkstra's algorithm, developed in 1956, sorts nodes by distance but is limited by the time it takes to sort.
- Researchers have long sought to overcome this sorting barrier, with recent success by Ran Duan and his team.
- The new algorithm clusters nodes and selectively uses the Bellman-Ford method to avoid sorting, improving efficiency.
- The algorithm works on both undirected and directed graphs, the latter being more complex due to one-way paths.
- The breakthrough could lead to further optimizations, as the new method's runtime isn't yet near any known fundamental limit.