科技圈变天！清华团队再次领先全球，突破困扰全球近70年难题

打开手机导航找路线，刷购物APP等快递，甚至打开网页加载数据，这些日常操作背后，都藏着同一个计算机科学的“老问题”：怎么找到两点之间的最短路径。

半个多世纪以来，大家都靠荷兰科学家1956年提出的Dijkstra算法解决这事，它就像算法界的“标准答案”。

可这标准答案有个致命短板，被一道叫“排序障碍”的无形墙卡了四十年，业内一直认为，这是图论领域绕不开的极限。

最近清华大学段然副教授带队，联合斯坦福大学研究者搞出的新算法，直接把这堵墙推倒了，这可不是小改进，以后咱们的导航响应、物流调度、网络传输，都可能因此变快一大截。

先给大伙说清楚，这“排序障碍”到底是个啥拦路虎：先把复杂的路线问题抽象成“图”，那些地点叫“节点”，连接地点的路叫“边”，路上的距离、时间就是“权重”。

算法的任务，就是从起点出发，算出到所有节点的最短路径。

Dijkstra算法的思路特直观，像个抠细节的导游，从起点出发，先摸清周边的节点，记好距离。

接着从所有没去过的节点里，挑个离起点最近的当“新据点”，再从这儿往外探索，一步一步推进，每次都选最近的节点，最后总能算出全局最优的路线。

但问题也出在这“每次都选最近的”上，这一步操作本质上就是“排序，得把所有候选节点按距离排好队，才能挑出最近的那个。

节点少的时候还好，一旦碰到城市交通网、全国物流线这种大场景，要排序的节点成百上千，速度立马就慢下来了。

1984年，普林斯顿大学的罗伯特・塔扬把Dijkstra算法优化到了极致，让它的效率摸到了排序的理论天花板，从那以后，“排序障碍”就成了铁律。

虽说有人在特殊场景下绕过它，比如所有路线权重都是整数的时候，但面对更普遍的任意权重图，谁也没办法。

清华团队的突破，核心就是换了个思路：不一定每一步都追求最优，照样能拿到最终的全局最优结果，他们放弃了Dijkstra算法那种“按顺序逐个处理”的洁癖，用了套更灵活的“宏观策略”，把好几招创新凑在了一起。

第一个关键招是“聚类”Dijkstra算法往外扩展时，要处理的候选节点会越来越多，像摊开的乱线团。新算法直接把这些前沿节点分成好几拨，每拨只挑一个代表性节点重点关注。

这么一来，每次要比较的节点数量少了一大半，效率自然提上去了。

第二个招是“借师学艺”，从另一种叫Bellman-Ford的算法里找灵感。

这算法平时比Dijkstra慢得多，但它有个优点，不用排序。新算法没把它全用上，只挑了开头几步来执行，相当于往图里派了批“侦察兵”。

这些侦察兵不纠结近处的小节点，专门找那些像交通枢纽一样的关键节点，先把这些枢纽的路径算出来，整个图的“骨架”就立住了，后面的计算跟着骨架走，自然省劲。

最后一步是“分层扩展”，新算法也像Dijkstra那样从内往外推进，但不较真“必须先处理近的节点”，它可能先算出远处某个枢纽的最短路径，再回头补全路上那些近的普通节点。

就因为不按常理出牌，才成功跳出了排序的束缚。

哥本哈根大学的计算机科学家米克尔・索鲁普评价这事时说，这算法特精妙的地方在于，没用到啥高深的数学工具，却解决了四十年的难题，看着就让人惊叹。

这突破不是拍脑袋来的，背后是近二十年的学术积累，还有一次跨洋合作的“神助攻”。

段然早在密歇根大学读博时，就对排序障碍产生了兴趣，他的导师正好是最早在特定图上突破这障碍的人，那时候起，他就埋下了攻克通用难题的种子。

2021年，段然想到了用聚类解决问题的新思路，打磨了一年，2022年秋天，他和研究生团队先搞出了适用于“无向图”的算法，就是那些边能双向走的图，首次在通用权重下突破了排序障碍。

但业内更关心的是更复杂的“有向图”，比如包含单行道的交通网，这才是更常见的场景。

转机出现在2023年夏天。斯坦福大学的研究生毛啸听了段然的学术报告，一下子被这研究吸引了。他自己琢磨了一阵，很快就和段然团队接上了头。

接下来几个月，两拨人靠线上会议碰想法，从Bellman-Ford算法里找突破口，毛啸还帮着把算法里的随机步骤改成了确定的方案。

最后那下“临门一脚”，是段然想起了自己2018年解决另一个图论问题的技术，把这技术加进去，所有碎片一下就拼成了完整的答案。

新算法不光能处理有向图，理论速度还超过了优化到极限的Dijkstra算法。

这事的意义，可比“多一个快算法”大多了，它直接打破了学界四十年的思维定势，说明了再成熟的领域也藏着创新的空间。

对咱们普通人来说，这突破早晚会落到实处，现在的导航偶尔会“卡壳”，尤其是早晚高峰的大城市路网，节点太多导致计算慢。

新算法普及后，导航能更快算出最优路线，绕路、堵车的概率可能都会降低。

物流行业更能受益，大物流公司的运输网遍布全国，要算的路径成千上万，算法快一秒，可能就能省出大量的时间和成本。

还有互联网的数据路由，网页加载、视频缓冲这些体验，都可能因为路径计算提速而变好。

更别说那些前沿领域了，北大团队之前搞存算一体架构时就提到，排序是AI、智能驾驶里特耗时的操作。

新算法说不定能和这些硬件技术结合，让自动驾驶的路径规划更实时，大模型的训练效率再上一个台阶。

从1956年Dijkstra算法诞生，到1984年塔扬设下排序障碍，再到2025年清华团队实现突破，这道算法难题跨越了近七十年。

它告诉我们，科学研究里没有永远的“不可能”，所谓的极限，往往是用来被打破的。