清华教授段然创新最短路径算法，打破计算机科学瓶颈

清华大学教授段然提出了一种全新的最短路径算法，这一突破性的成果超越了教科书中经典的Dijkstra算法。

计算机科学的重大突破！

清华大学教授刷新最短路径算法认知，或将重塑计算机算法教科书。

在计算机科学领域，寻找网络中各点的最短路径是一个经典问题，而Dijkstra算法则是解决这一问题的经典方法。

自1956年以来，最短路径问题吸引了众多研究者的关注。

哥本哈根大学计算机科学家Mikkel Thorup表示:

最短路径是个引人入胜的好问题，全世界的人都能感同身受。

直觉上，找到离起点最近的点的路径应该最简单。

因此，若想设计解决最短路径问题的最快算法，合理的做法是首先找到最近的点，然后是次近的点，以此类推。但这意味着你需要反复确定哪个点是最近的，也就是说，你得按距离给这些点排序。

然而，这种方法有一个根本的限制：这种算法的速度无法快过排序所需的时间。

四十年前，研究最短路径算法的科学家们遇到了这个「排序瓶颈」。

现在，来自清华大学等机构的研究团队设计了一种新算法，突破了这一瓶颈。这种算法不依赖排序，而且比任何需要排序的算法运行得更快。

论文链接：https://arxiv.org/abs/2504.17033

普林斯顿大学的计算机科学家Robert Tarjan说：「这些研究者大胆地认为他们能打破这个瓶颈。这是一个惊艳的成果。」

值得一提的是，这项研究摘得STOC最佳论文，实至名归。

最短路径

若想解决复杂难题，条理分明往往事半功倍。例如将问题拆解后优先处理最简单的部分——但这种分类需要代价，你可能耗费过多时间在排序上。

这一困境在计算机科学中最经典的问题之一中尤为明显：如何在网络中从特定起点出发，找到通往其他所有点的最短路径。这就像日常搬家后必须解决的升级版问题：规划从新家到公司、健身房和超市的最佳路线。

为了从数学角度分析最短路径问题，研究者们使用图论的语言——图是由点（或称节点）组成的网络，这些点通过线连接起来。每条连接线都标有一个数字，叫作权重，它可以代表这段线的长度或穿越它所需的时间。

通常，任意两个节点之间都有很多路径，最短路径就是那些权重加起来最小的路径。给定一个图和一个特定的「起点」，算法的目标就是找到到其他每个节点的最短路径。

Dijkstra算法如何找到最短路径

Dijkstra算法从网络中的一个特定点开始，找到到每个其他点的最短路径。它按距离从近到远的顺序找到这些路径。

超越排序

段然对排序瓶颈的关注可以追溯到近20年前。

希望之路

随机性如何优化算法

层进式革新