本科必學Dijkstra算法被超越！清華段然團隊打破圖靈獎得主證明的普遍最優性

白交 2025-08-09 15:04:41 來源：量子位

白交 發自 凹非寺

量子位 | 公眾號 QbitAI

本科經典算法Dijkstra，被清華團隊超越了！

這個被用來解決最短路徑問題的經典算法，去年才被圖靈獎得主Tarjan團隊證明具有普遍最優性。

但現在，來自清華的段然團隊將這一格局徹底打破——

運行速度比任何Dijkstra及其改進算法都快，關鍵是它徹底解決了困擾研究人員四十多年來的“排序障礙”。因為它壓根就不進行排序

。

該算法改進了圖靈獎得主Tarjan提出的O(m + nlogn)算法，后者在1984年將Dijkstra原始算法探索到了速度極限。

而更快的最短路徑算法，不管是在理論上和實際應用中都有很大意義，參考Dijkstra算法就知道了。Dijkstra算法在廣泛地應用于我們的日常生活中，例如地圖APP，Dijkstra算法就被用來計算從用戶當前位置到目的地的最優路線。而在計算機網絡中也被廣泛應用于路由協議中。

這一進展被曝光，一時間引發了不少關注。

也有人不吝贊美：這是一個重要的里程碑。

但也有人認為，對大模型來說可能是個挫折，尤其在GPT-5發布之際，因為我們總是期待AI能發現這些突破性進展。

GPT-5已經準備好編碼了。

找到最佳路線的最快方法

找到從網絡中特定起點到其他每個點的最短路徑。有科學家曾形容這個標志性問題，最短路徑是一個世界上任何人都能理解的美麗問題。

從數學角度來分析問題，研究人員更傾向于用節點組成的網絡，通過線段連接起來，然后找到通往每個節點的最短路徑。

但過去一直以來，任何遵循這種方法的算法都有一個基本的速度限制：你的速度不可能比排序所需的時間更快。

因為如果你想解決一個棘手的問題，整理思路通常很有幫助。比如，你可以把問題分解成幾個部分，先解決最簡單的部分。但這種整理是有代價的。你可能會花費太多時間去整理這些碎片。

這就像你每次搬家時可能需要思考從新家到工作地點、健身房和超市的最佳路線。

最經典的最短路徑算法就是Dijkstra。這是計算機專業本科生都在學的算法，它的思路是從源頭開始，逐步向外推進——

通過掃描該區域的 “邊界”， 來決定下一步要去哪里。這最初并不需要花費太多時間，但隨著算法的推進，速度會變得越來越慢。

過去一直有人在這個算法上進行改進，但都達到了速度限制。于是乎，這項研究停止了很長時間，很多人認為沒有更好的方法。沒想到的是，這個問題困住了研究員們接近半世紀。

去年，圖靈獎得主Robert Tarjan及合作者發表的論文證明了Dijkstra算法對于“最短路徑排序問題”的普遍最優性，獲得了FOCS 2024的最佳論文獎。

直到清華大學段然團隊的新算法打破了這一局面，新算法避免了整體排序，得到了比Dijkstra算法更快的最短路徑問題的算法。

他設想將邊界上相鄰的節點分組成簇。然后，他只考慮每個簇中的一個節點。由于需要篩選的節點更少，搜索在每一步都可以更快。算法也可能最終到達最近節點以外的地方，因此排序障礙不再適用。

但是，確保這種基于簇的方法實際上使算法更快而不是更慢將是一個挑戰。

2022年秋天，他找了三位研究生來幫助解決細節問題，接個月后得到部分解決方案：新算法可以打破任何權重的排序障礙，但僅限于無向圖。

時間來到2023年夏天，段然教授在加州某一會議上分享無向圖算法 時遇到了毛嘯，兩人相談甚歡，隨后紛紛繼續展開了探索。

他們從另一個著名的最短路徑問題算法中汲取了靈感，這就是Bellman-Ford算法，它不產生有序列表。

乍看之下，Bellman-Ford算法比Dijkstra的算法慢得多，似乎不具備參考價值。但在他們的嘗試下，只運行幾步就能避免Bellman-Ford算法的緩慢問題。這樣一來，他們就借著往后續步驟進行探索。

2024年3月，毛某設計了一種用無需隨機性的新方法來解決最短路徑問題。隨后正式加入了 團隊。后來段然意識到他們可以借鑒2018年設計的一個算法。它適用于不同的圖問題。也許可以突破排序瓶頸。

這一技術正是他們所需的最后一塊拼圖，使算法在有向圖和無向圖上的運行速度均快于Dijkstra算法。

最終這一算法，將圖切分成多層，然后同Dijkstra算法一樣從從源頭向外擴展。

但它不是在每一步都處理整個邊界，而是使用 Bellman-Ford 算法來精確定位有影響力的節點。

從這些節點出發，向前移動，找到通往其他節點的最短路徑，然后再返回到其他邊界節點。

它并不總是按照距離遞增的順序在每一層中找到節點，因此排序障礙并不適用。如果你以正確的方式切分圖，它的運行速度會比Dijkstra算法的最佳版本略快。

它的算法要復雜得多，依賴于許多需要完美組合的片段。但奇怪的是，這片段都沒有使用復雜的數學原理。

段然和他的團隊計劃探索簡化該算法的可能性，使其運行速度更快。

隨著排序障礙的消除，新算法的運行時間已接近計算機科學家所知的任何基本極限。

有人表示，這玩意兒或許50年前就被發現了，也正因此，這一結果才顯得多么印象深刻。

圖靈獎得主普林斯頓大學Tarjan教授就放話了，

作為一個樂觀主義者，如果能更進一步簡化和提效，我不會感到驚訝。我絕對不認為這是這個過程的最后一步。

清華段然團隊

這篇論文在理論計算機國際頂級會議STOC 2025上獲得最佳論文獎。

清華大學交叉信息院副教授段然為論文通訊作者，研究方向包括圖論算法、數據結構、計算理論。

他本科畢業于清華計算機系，隨后前往密歇根大學攻讀博士學位。畢業后又在馬克斯普朗克信息學研究所搞博士后研究。

他對排序屏障的興趣可以追溯到近20年前他在密歇根大學攻讀研究生期間，當時他的導師是那些在特定情況下破解該屏障的研究人員之一。

其他作者包括姚班2019屆本科畢業生束欣凱，以及姚班畢業生、交叉信息院2022級博士生毛嘉怡和2021級博士生尹龍暉。

此外斯坦福大學2022級博士生毛嘯也作出了貢獻。

參考鏈接：
[1]https://www.tsinghua.edu.cn/info/1175/118821.htm
[2[https://x.com/deedydas/status/1953841151645266091
[3]https://www.alphaxiv.org/abs/2504.17033
[4]https://news.ycombinator.com/item?id=44812695
[5]https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
[6]https://x.com/Tsinghua_Uni/status/1925869533077610935