打开网易新闻 查看更多视频
一个用了41年的算法，被一群清华人给破了。
从1984年到现在，Dijkstra算法一直是计算最短路径的"标准答案"。你每天用的Google Maps导航、外卖平台的路径规划、物流系统的配送路线，底层都是它在支撑。
但问题是，这个算法有个理论上的天花板。去年，算法界的传奇人物Robert Tarjan还专门拿了个奖，证明Dijkstra在数学上已经是理论最优，没法再快了。
全世界最聪明的几颗脑袋，都默认这道"排序屏障"绕不过去。
清华团队换了个思路：找最短路径，干嘛非要把所有点都排个序？
他们把Bellman-Ford的逻辑和递归部分排序的方法拼在一起，搞出了一个新算法，复杂度降到了O(m log^{2/3} n)。
官方意义上，确实比Dijkstra更快。
放在小图里，你感觉不到差别。但在网页级别的超大规模图、全球物流网络这种场景下，这个差距是真实存在的。
明天早上你的GPS导航不会突然变快，但整个最短路径问题的底层逻辑，已经在很多领域发生了根本性的变化。
打开网易新闻 查看精彩图片
这件事的意义不在于"快了多少"，而在于证明了一件事：那些被认为"不可能突破"的理论边界，可能只是因为大家一直在同一条路上走。
换个方向，路就出来了。
热门跟贴