清华大学教授段然提出了一种最短路径新方法，击败了教科书中经典的Dijkstra算法。 计算机科学的重大成果！ 清华大学教授刷新最短路径算法认知，或将改写计算机算法教科书。 四十年前，研究最短路径算法的科学家们遇到了这个「排序瓶颈」。 现在，来自清华大学等机构的研究团队设计了一种新算法，突破了这一瓶颈。这种算法不依赖排序，而且比任何需要排序的算法运行得更快。 在计算机科学中，一个经典问题是寻找网络中每个点的最短路径，而Dijkstra算法是此问题的最经典解决方法。 自1956年来，最短路径问题吸引了众多研究人员的关注。 哥本哈根大学计算机科学家Mikkel Thorup米克尔·索鲁普表示: 最短路径是个绝妙的好问题，全世界人都能感同身受。 直觉上，找到离起点最近的点的路径应该最简单。 因此，如果想设计一个解决最短路径问题的最快算法，合理的做法是先找到最近的点，然后是次近的点，依此类推。但这意味着你需要反复确定哪个点是 最近的，也就是说，你得按距离给这些点排序。 然而，这种方法有一个根本的限制：这种算法的速度无法快过排序所需的时间。 论文链接：https://arxiv.org/abs/2504.17033 普林 ...

每次打开导航的，导航软件在一秒内给出一个最速路线的时候，你有没有好奇过它是怎么找到这条路的？ 假如不考虑堵车、红绿灯等交通影响因素，仅找到一条最短最快的路线，那不论如何也逃不掉 Dijkstra 算 法。 按照传统的 Dijkstra 算法，你将在整段路程中停下多次，寻找每一段的最短路径，然后再去更新下一段如何 最短，直到走到目的地。在抉择的过程中会面临着不断选择「最短」路径的情形，还需要通过对比排序来 决策。 机器之心报道 机器之心编辑部 Dijkstra 算法有多经典呢？ 可以说每一个学计算机的学生，甚至每一个学编程理论或数据结构的人，都会在教科书上看到这个算法。 其在计算机学生心中地位甚至不亚于物理学中的基本定律，想到路径最短，必然想到 Dijkstra。 不过，现在有种方法能直接让你跳过不必要的排序，只专注于最重要的点之间的最短距离，大大缩短了所 需要的计算时间。这就是清华交叉信息研究院段然团队一项重磅研究给出的全新解法。这项研究还在理论 计算机国际顶级会议 STOC 2025 上获得最佳论文奖。 该算法改进了图灵奖得主 Robert Tarjan 等人在 1984 年提出的 O(m + nlogn) ...

白交 发自 凹非寺 量子位 | 公众号 QbitAI 本科经典算法Dijkstra，被清华团队超越了！ 这个被用来解决最短路径问题的经典算法，去年 才被图灵奖得主Tarjan团队证明具有普遍最优性 。 但现在，来自清华的段然团队将这一格局彻底打破—— 运行速度比任何Dijkstra及其改进算法都快，关键是它彻底解决了困扰研究人员四十多年来的"排序障碍"。因为它压根就不进行排序 。 该算法改进了图灵奖得主Tarjan提出的O(m + nlogn)算法，后者在1984年将Dijkstra原始算法探索到了速度极限。 而更快的最短路径算法，不管是在理论上和实际应用中都有很大意义，参考Dijkstra算法就知道了。Dijkstra算法在广泛地应用于我们的日常 生活中，例如地图APP，Dijkstra算法就被用来计算从用户当前位置到目的地的最优路线。而在计算机网络中也被广泛应用于路由协议中。 这一进展被曝光，一时间引发了不少关注。 也有人不吝赞美：这是一个重要的里程碑。 GPT-5已经准备好编码了。 但也有人认为，对大模型来说可能是个挫折，尤其在GPT-5发布之际，因为我们总是期待AI能发现这些突破性进展。 找到最佳路线 ...