@HowToAI_：中國研究團隊打破41年最短路徑演算法紀錄。 清華大學研究團隊發表論文，證明Dijkstra演算法並非最優，開發出有向圖單源最短路徑（SSSP）的新確定性演…

中國研究團隊打破41年最短路徑演算法紀錄。 清華大學研究團隊發表論文，證明Dijkstra演算法並非最優，開發出有向圖單源最短路徑（SSSP）的新確定性演算法，時間複雜度達O(m log²/³ n)，首次擊破1984年以來O(m + n log n)的排序屏障。 歷史背景與Dijkstra霸權 Dijkstra演算法自1959年問世以來，超過40年來一直是單源最短路徑（SSSP）的無敵王者，用於Google Maps、航班預訂或網際網路封包路由等應用。自1984年起，教科書認定其效率受「排序屏障」限制：求最短路徑需按距離排序節點，而排序有不可逾越的數學下界O(n log n)。即使天才演算法專家Robert Tarjan去年（2024年）獲獎，證明若需輸出按距離排序的節點順序，Dijkstra即為最優，但團隊直接挑戰：停止排序。 新演算法的核心突破 團隊結合Bellman-Ford演算法邏輯與革命性「遞迴部分排序」（recursive partial ordering）方法，避免完整排序節點。論文《Breaking the Sorting Barrier for Directed Single-Source Shortest Paths》（作者：Ran Duan、Jiayi Mao、Xiao Mao、Xinkai Shu、Longhui Yin，2025年7月31日）證明： 首次自1984年以來，對SSSP問題的確定性改進。 新時間複雜度O(m log²/³ n)，正式擊敗長期O(m + n log n)界限。 在巨型稀疏圖（如網頁圖或全球物流網路）上，尋找最佳路徑遠快於以往想像可能。 這是理論電腦科學的巨大轉變，四十年來演算法界視此界限為絕對，現被推翻，最經典圖論問題再度敞開。 技術細節與創新方法 傳統Dijkstra使用優先佇列（搭配Fibonacci heap等資料結構），每次提取源點最近的節點u，放鬆其出邊，時間O(m + n log n)，在比較-加法模型（comparison-addition model）下運作，仅允許邊權重比較與加法，每操作耗時1單位。Bellman-Ford則基於動態規劃，放鬆所有邊k次，求最多k邊路徑只需O(mk)時間，無需排序。 團隊方法融合兩者，透過遞迴分割技術（類似瓶頸路徑演算法[GT88, CKT+16, DLWX18]）： Dijkstra執行中，優先佇列維持「邊界」S：若節點u「不完整」（當前估計bd[u] > 真實d(u)），則s-u最短路徑必經S中某「完整」v，稱u依賴v。 瓶頸：邊界S偶達Θ(n)大小，需維持總順序，無法破Ω(n log n)排序屏障。 邊界縮減的核心idea 假設計算距離小於上界B的所有路徑，讓eU為d(u) < B且s-u路徑訪S的節點集。給定k = log^Ω(1)(n)，限|S| ≤ |eU| / k（即興趣節點的1/log^Ω(1)(n)）： 若|eU| > k|S|，邊界已小至|eU|/k。 否則，|eU| ≤ k|S|：從S執行Bellman-Ford k步，所有s-u路徑含<eU中<k節點的u即完整；否則u依賴的v，其最短路徑樹含≥k eU節點，將S縮至「樞紐」（pivots），數量≤|eU|/k。 演算法非動態Dijkstra，而是分治程序：log(n/t)層，每層有邊界集與上界B。朴素實作每邊界節點花Θ(t)時間，總時間Θ(log n / vertex)；但每層施加邊界縮減，僅對1/log^Ω(1)(n)的樞紐做Θ(t)工作，每節點時間降至log n / log^Ω(1)(n)，顯著加速。 與既有方法的比較 定論1.1：確定性O(m log²/³ n)時間解有向圖真實非負邊權SSSP，為稀疏圖首破排序瓶頸。 [DMSY23]有O(m √(log n log log n))隨機演算法（無向圖），優於稀疏圖O(n log n)；本作為有向圖首例，且確定性（連無向圖確定性紀錄也破）。 無向圖：[PR05]階層演算法O(m α(m,n) + min{n log n, n log log r})，α為反Ackermann函數，r為邊權比。 [HHR+24]證Dijkstra輸出距離排序時最優；本作僅求距離不排序，故能突破。 實際限制與理論價值 這是漸近（asymptotic）勝利，非工程實作優化： 對實際圖，Dijkstra + 二元堆或Fibonacci heap仍快得多，常數因子小、實作簡單，新演算法理論價值大於實務。 僅稀疏圖（m = Θ(n)）嚴格勝出：O(m log²/³ n) 擊敗 O(m + n log n)；稠密圖（m = Θ(n²)）Dijkstra的O(m)項主導，新法無優勢。 簡言之：理論複雜度贏Dijkstra，日常實務仍用Dijkstra。 更廣影響與反思 若基本圖論40年定律可破，其他「不可能」速度界限待粉碎？如網際網路路由、物流優化、AI路徑規劃等，將受啟發。論文重開定錨已久的領域，提醒演算法界：經典不等於不可超越，清華團隊以「停止排序」顛覆共識，預示理論突破將持續推動實務邊界前移。 原文：https://easyvibecoding.app/curated/1202