@lxfater: Researchers from Tsinghua University have surpassed the algorithm Google Maps has used for 41 years. From 1984 to the present, no one had managed to do so in 41 years. That algorithm is called Dijkstra. It doesn't matter if you haven't heard of it; you use it every day. However, it has been stuck for 40 years without breakthrough because of a mathematical sorting barrier standing in the way...

Researchers from Tsinghua University have surpassed the algorithm Google Maps has relied on for 41 years. From 1984 to the present, no one had managed to achieve this in 41 years. That algorithm is called Dijkstra. It doesn't matter if you haven't heard of it; you use it every day. However, progress was stalled for 40 years because a mathematical sorting barrier stood in the way. The smartest minds in the world assumed this barrier was insurmountable. Last year, algorithm legend Robert Tarjan even won an award for proving that Dijkstra's algorithm was theoretically optimal. It seemed like a breakthrough was impossible, right? But these researchers at Tsinghua took a different path. Their idea was simple: why do you need to sort all the nodes when finding the shortest path? By combining the logic of the Bellman-Ford algorithm with a method called recursive partial sorting, they achieved a complexity of O(m log^{2/3} n). Officially, this is faster than Dijkstra's algorithm. You won't notice the difference on small graphs, but in large-scale scenarios like web-scale or global logistics, this gap is real. Your GPS won't suddenly get faster tomorrow morning, but this development marks a fundamental shift in the field of shortest-path problems.