本科必學(xué)Dijkstra算法被超越！清華段然團(tuán)隊(duì)打破圖靈獎(jiǎng)得主證明的普遍最優(yōu)性

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

白交 發(fā)自 凹非寺

量子位 | 公眾號(hào) QbitAI

本科經(jīng)典算法Dijkstra，被清華團(tuán)隊(duì)超越了！

這個(gè)被用來解決最短路徑問題的經(jīng)典算法，去年才被圖靈獎(jiǎng)得主Tarjan團(tuán)隊(duì)證明具有普遍最優(yōu)性。

但現(xiàn)在，來自清華的段然團(tuán)隊(duì)將這一格局徹底打破——

運(yùn)行速度比任何Dijkstra及其改進(jìn)算法都快，關(guān)鍵是它徹底解決了困擾研究人員四十多年來的“排序障礙”。因?yàn)樗鼔焊筒贿M(jìn)行排序

。

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

而更快的最短路徑算法，不管是在理論上和實(shí)際應(yīng)用中都有很大意義，參考Dijkstra算法就知道了。Dijkstra算法在廣泛地應(yīng)用于我們的日常生活中，例如地圖APP，Dijkstra算法就被用來計(jì)算從用戶當(dāng)前位置到目的地的最優(yōu)路線。而在計(jì)算機(jī)網(wǎng)絡(luò)中也被廣泛應(yīng)用于路由協(xié)議中。

這一進(jìn)展被曝光，一時(shí)間引發(fā)了不少關(guān)注。

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

但也有人認(rèn)為，對(duì)大模型來說可能是個(gè)挫折，尤其在GPT-5發(fā)布之際，因?yàn)槲覀兛偸瞧诖鼳I能發(fā)現(xiàn)這些突破性進(jìn)展。

GPT-5已經(jīng)準(zhǔn)備好編碼了。

找到最佳路線的最快方法

找到從網(wǎng)絡(luò)中特定起點(diǎn)到其他每個(gè)點(diǎn)的最短路徑。有科學(xué)家曾形容這個(gè)標(biāo)志性問題，最短路徑是一個(gè)世界上任何人都能理解的美麗問題。

從數(shù)學(xué)角度來分析問題，研究人員更傾向于用節(jié)點(diǎn)組成的網(wǎng)絡(luò)，通過線段連接起來，然后找到通往每個(gè)節(jié)點(diǎn)的最短路徑。

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

因?yàn)槿绻阆虢鉀Q一個(gè)棘手的問題，整理思路通常很有幫助。比如，你可以把問題分解成幾個(gè)部分，先解決最簡單的部分。但這種整理是有代價(jià)的。你可能會(huì)花費(fèi)太多時(shí)間去整理這些碎片。

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

最經(jīng)典的最短路徑算法就是Dijkstra。這是計(jì)算機(jī)專業(yè)本科生都在學(xué)的算法，它的思路是從源頭開始，逐步向外推進(jìn)——

通過掃描該區(qū)域的 “邊界”， 來決定下一步要去哪里。這最初并不需要花費(fèi)太多時(shí)間，但隨著算法的推進(jìn)，速度會(huì)變得越來越慢。

過去一直有人在這個(gè)算法上進(jìn)行改進(jìn)，但都達(dá)到了速度限制。于是乎，這項(xiàng)研究停止了很長時(shí)間，很多人認(rèn)為沒有更好的方法。沒想到的是，這個(gè)問題困住了研究員們接近半世紀(jì)。

去年，圖靈獎(jiǎng)得主Robert Tarjan及合作者發(fā)表的論文證明了Dijkstra算法對(duì)于“最短路徑排序問題”的普遍最優(yōu)性，獲得了FOCS 2024的最佳論文獎(jiǎng)。

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

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

但是，確保這種基于簇的方法實(shí)際上使算法更快而不是更慢將是一個(gè)挑戰(zhàn)。

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

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

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

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

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

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

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

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

從這些節(jié)點(diǎn)出發(fā)，向前移動(dòng)，找到通往其他節(jié)點(diǎn)的最短路徑，然后再返回到其他邊界節(jié)點(diǎn)。

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

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

段然和他的團(tuán)隊(duì)計(jì)劃探索簡化該算法的可能性，使其運(yùn)行速度更快。

隨著排序障礙的消除，新算法的運(yùn)行時(shí)間已接近計(jì)算機(jī)科學(xué)家所知的任何基本極限。

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

圖靈獎(jiǎng)得主普林斯頓大學(xué)Tarjan教授就放話了，

作為一個(gè)樂觀主義者，如果能更進(jìn)一步簡化和提效，我不會(huì)感到驚訝。我絕對(duì)不認(rèn)為這是這個(gè)過程的最后一步。

清華段然團(tuán)隊(duì)

這篇論文在理論計(jì)算機(jī)國際頂級(jí)會(huì)議STOC 2025上獲得最佳論文獎(jiǎng)。

清華大學(xué)交叉信息院副教授段然為論文通訊作者，研究方向包括圖論算法、數(shù)據(jù)結(jié)構(gòu)、計(jì)算理論。

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

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

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

此外斯坦福大學(xué)2022級(jí)博士生毛嘯也作出了貢獻(xiàn)。

參考鏈接：
[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