作者:
yam276 ('_')
2025-08-11 18:38:32清華大學突破Dijkstra演算法瓶頸
https://arxiv.org/pdf/2504.17033
Dijkstra演算法是找網路中每個點的最短路徑時的最經典算法(資工系必學)
自1956年來科學家們遭遇了理論瓶頸:如果想設計解決最短路徑問題的最快算法
需先找到距離起點最近的點
這需要按距離排序這些點
這導致演算法速度無法快過排序所需時間
在斬獲理論計算機國際頂級會議STOC 2025最佳論文獎的作品中
北京清華學者發布不依賴排序的新演算法
打破持續數十年Dijkstra演算法理論瓶頸
他們用貝爾曼-福特演算法定位關鍵節點後優先探索
接著回溯處理其他邊界節點
由於不嚴格按距離順序探索每層節點
排序障礙自然失效
若採用恰當分層策略
其速度略超優化版Dijkstra演算法
新演算法運作效率已遠超現有理論極限
任何依賴大量最短路徑運算的系統都將受益
這將為資料中心節省大量CPU運算資源