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

Core Viewpoint - The article discusses a groundbreaking research by a team from Tsinghua University that presents a new algorithm for finding the shortest path in directed graphs, which significantly improves upon the traditional Dijkstra algorithm by eliminating unnecessary sorting steps, thus reducing computational complexity [9][13][17]. Summary by Sections Dijkstra Algorithm Overview - Dijkstra's algorithm, introduced in 1956, is a classic method for finding the shortest path from a source node to all other nodes in a graph, widely used in various applications such as network routing and map navigation [11]. - The algorithm operates by continuously selecting the current shortest node and updating the distances to its adjacent nodes until all shortest paths are found [11][17]. New Research Breakthrough - The new algorithm developed by the Tsinghua team breaks the O(m + n log n) time complexity barrier established by Dijkstra's algorithm for sparse graphs, demonstrating that Dijkstra is not the optimal choice for single-source shortest path (SSSP) problems [17][18]. - The research introduces a deterministic O(mlog2/3n) time algorithm for SSSP in directed graphs with non-negative real edge weights, marking a significant advancement in the field [17][18]. Methodology and Implementation - The new approach focuses on calculating distances without the need for sorting, utilizing a layered recursive method to group nodes and only perform detailed shortest path calculations on key nodes [13][14]. - The algorithm employs a divide-and-conquer strategy, reducing the size of the frontier set of nodes and thus minimizing the computational overhead associated with maintaining a globally ordered set of nodes [22][24]. Technical Details - The algorithm is designed to handle constant-degree graphs and operates under a comparison-addition model, where each operation takes unit time [17][19]. - It introduces a bounded multi-source shortest path (BMSSP) problem, allowing for efficient distance calculations without the need for sorting all nodes [24][27]. Conclusion - This research not only enhances the efficiency of shortest path calculations but also opens new avenues for further exploration in graph algorithms, potentially impacting various fields that rely on efficient routing and pathfinding solutions [9][13].

Core Viewpoint - A new algorithm developed by a team from Tsinghua University has surpassed Dijkstra's algorithm in speed for solving the shortest path problem, addressing a long-standing "sorting barrier" that has hindered advancements in this area for over 40 years [2][19][32]. Summary by Sections Algorithm Development - The new algorithm improves upon the O(m + n log n) algorithm proposed by Turing Award winner Robert Tarjan in 1984, which was considered the speed limit for Dijkstra's original algorithm [5][18]. - The Tsinghua team’s approach avoids overall sorting by clustering adjacent nodes on the boundary, allowing for faster searches with fewer nodes to consider [19][29]. Historical Context - Dijkstra's algorithm is widely used in applications such as mapping services and computer network routing protocols, making improvements in this area significant for both theoretical and practical applications [5][13]. - The sorting barrier has historically limited the speed of algorithms that follow a node-based network approach, as sorting time cannot be surpassed [15][18]. Technical Insights - The new algorithm segments the graph into layers and utilizes the Bellman-Ford algorithm to accurately identify influential nodes, thus bypassing the sorting barrier [28][29]. - The complexity of the new algorithm relies on a combination of simpler components rather than advanced mathematical principles, which may allow for further simplification and speed enhancements [30][31]. Recognition and Future Directions - The breakthrough has garnered significant attention, with some experts calling it an important milestone in computer science [6][9]. - The Tsinghua team plans to explore possibilities for further simplifying the algorithm to enhance its speed even more [31][35].