@lxfater: 清华几个人把 Google Maps 用了 41 年的算法给超了 从 1984 年算到现在，41 年没人做到过 那个算法叫 Dijkstra，你没听过没关系，你每天都在用 但这个卡了 40 年突破不了，因为有一道数学上的排序屏障横在中间 …

X AI KOLs Timeline 新闻
algorithms computer-science tsinghua-university shortest-path dijkstra-algorithm

摘要

Researchers from Tsinghua University have developed a new shortest-path algorithm with O(m log^{2/3} n) complexity, surpassing Dijkstra's algorithm which had been considered theoretically optimal for 41 years.

清华几个人把 Google Maps 用了 41 年的算法给超了 从 1984 年算到现在，41 年没人做到过 那个算法叫 Dijkstra，你没听过没关系，你每天都在用 但这个卡了 40 年突破不了，因为有一道数学上的排序屏障横在中间 全世界最聪明的几个脑袋都默认这玩意儿绕不过去 去年算法界传奇 Robert Tarjan 还专门拿了个奖 证明 Dijkstra 已经是理论最优 这事看起来已经没法突破了，对不对？ 但清华这帮人不走这条路 他们的想法很简单: 找最短路径，干嘛非要把所有点都排个序 把 Bellman-Ford 那套逻辑，跟一种叫递归部分排序的方法拼起来,最后跑出来 O(m log^{2/3} n) 的复杂度 官方意义上比 Dijkstra 更快,放在小图上你感觉不到差别 但在网页级、全球物流级的大图里，这个差距是真实存在的 明天早上你的 GPS 不会突然变快 但整个最短路径问题的在很多领域发生了根本性的变化
查看原文

相似文章

25+ years of pathfinding problems with C++

Lobsters Hottest

《帝国时代》工程总监深入剖析了系列游戏 25 年来寻路系统的技术债，指出遗留代码、动态地图机制及 SIMD 指令集取代 x87 扩展精度导致的浮点误差是单位“穿墙”等经典 Bug 的根源。