一個用了41年的算法,被一群清華人給破了。
從1984年到現在,Dijkstra算法一直是計算最短路徑的"標準答案"。你每天用的Google Maps導航、外賣平臺的路徑規劃、物流系統的配送路線,底層都是它在支撐。
但問題是,這個算法有個理論上的天花板。去年,算法界的傳奇人物Robert Tarjan還專門拿了個獎,證明Dijkstra在數學上已經是理論最優,沒法再快了。
全世界最聰明的幾顆腦袋,都默認這道"排序屏障"繞不過去。
清華團隊換了個思路:找最短路徑,干嘛非要把所有點都排個序?
他們把Bellman-Ford的邏輯和遞歸部分排序的方法拼在一起,搞出了一個新算法,復雜度降到了O(m log^{2/3} n)。
官方意義上,確實比Dijkstra更快。
放在小圖里,你感覺不到差別。但在網頁級別的超大規模圖、全球物流網絡這種場景下,這個差距是真實存在的。
明天早上你的GPS導航不會突然變快,但整個最短路徑問題的底層邏輯,已經在很多領域發生了根本性的變化。
![]()
這件事的意義不在于"快了多少",而在于證明了一件事:那些被認為"不可能突破"的理論邊界,可能只是因為大家一直在同一條路上走。
換個方向,路就出來了。
特別聲明:以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布,本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.