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