比 Dijkstra 更快？

背景

這場討論源於一篇探討新型最短路徑演算法的研究。該演算法宣稱突破了經典戴克斯特拉演算法（Dijkstra's algorithm）的「排序障礙」，在理論複雜度上優於這項統治電腦科學界超過六十年的基準。作者身為網路系統教科書編纂者，從工程實務角度質疑這種理論上的進步是否真能改變現有的路由協議與硬體實作。

社群觀點

Hacker News 的討論呈現出理論研究與工程實務之間的巨大鴻溝。許多留言者指出，這項新研究在學術上極具價值，因為它在漸近複雜度（Big-O）上取得了突破，將複雜度從 $O(m \log n + m)$ 降至 $O(m \log^{2/3} n)$。然而，從純數學角度看，這種進步雖然令人興奮，但在現實世界的網路拓撲中卻未必實用。有網友精確計算後發現，該演算法對圖形的稀疏程度有極高要求，若節點的平均度數超過 3.5，其表現反而可能不如戴克斯特拉演算法。這意味著在大多數具有高度連通性的現代網路架構中，新演算法可能缺乏競爭力。

在實務層面，社群普遍認同作者的觀點：演算法的執行時間往往不是系統效能的瓶頸。多位具備路由器開發經驗的工程師提到，在真實的路由收斂過程中，故障檢測（如 BFD 協議）、鏈路狀態封包的傳播延遲，以及更新轉發表（FIB）所花費的時間，都遠比計算最短路徑的幾毫秒更為關鍵。此外，當網路規模僅在數千個節點的等級時，傳統演算法的常數項優勢通常會壓倒新演算法在理論上的擴展性。這也引發了關於「過度工程」的討論，即追求極致的理論優化是否會導致系統過於複雜而難以維護。

另一部分的討論則轉向了計算模型的本質。有觀點認為，現代電腦硬體的特性（如快取機制、記憶體層級）使得傳統的複雜度分析逐漸失真。例如，當 $n$ 變得極大時，記憶體存取的時間受限於物理空間與光速，實際上會呈現立方根的增長，而非理想模型中的常數時間。此外，關於「排序」是否真的能被完全避開也存在爭論。有留言者指出，如果輸入數據具有特定屬性（如有限位元長度），基數排序（Radix Sort）本就能達到線性時間，因此所謂的「排序障礙」在某些特定硬體環境下本就不存在。

最後，社群對這類理論突破抱持一種「有用但不一定好用」的共識。正如研究 NP 完全性（NP-Completeness）能告訴工程師何時該放棄尋找完美解，這項新研究的價值在於定義了問題的理論極限。雖然它短期內不會取代 OSPF 或 IS-IS 協議中的戴克斯特拉實作，但它為未來處理超大規模稀疏圖形（如社交網路或生物資訊圖譜）提供了新的工具箱。

延伸閱讀

• 系統方法論教科書：由原文作者參與編寫的網路系統教材《Computer Networks: A Systems Approach》，提供免費線上版本。
• 原始研究論文：發表於 ACM STOC 會議的論文《Faster Shortest Paths in Dense Graphs》，詳細描述了該演算法的數學證明。
• Quanta Magazine 報導：針對該演算法突破的科普性深度報導，解釋了其如何避開傳統排序的邏輯。
• XSUM 演算法：留言中提到的關於浮點數精確求和的優化演算法，適用於對精度要求極高的數值計算場景。