Hacker News
This repository provides a high-performance C99 implementation of the DMMSY algorithm from STOC 2025, which breaks the sorting barrier for directed single-source shortest paths and achieves massive speedups over Dijkstra.
AI 生成摘要
本專案提供了 STOC 2025 論文中 DMMSY 演算法的高效能 C99 實作，打破了有向單源最短路徑的排序瓶頸，並在效能上大幅超越傳統的 Dijkstra 演算法。
這篇討論源於開發者 danalec 在 GitHub 上發布的一個 C99 實作專案，該專案宣稱實作了 STOC 2025 最佳論文獎的研究成果。這項由 Ran Duan 等人提出的演算法，旨在打破迪傑斯特拉（Dijkstra）演算法維持長達 65 年的 $O(m + n \log n)$ 複雜度瓶頸，將單源最短路徑（SSSP）的複雜度優化至 $O(m \log^{2/3} n)$。該實作採用遞迴子問題分解而非全域優先隊列，並在 GitHub 頁面上宣稱在處理大規模稀疏圖形時，效能比標準 Dijkstra 實作快上兩萬倍。
儘管這項演算法在理論界獲得高度評價，但 Hacker News 社群對此實作的效能數據與真實性展現了顯著的質疑。討論的核心集中在理論複雜度與實際運行速度之間的巨大落差。有評論者指出，從數學角度來看，當節點數為一百萬時，$O(\log^{2/3} n)$ 與 $O(\log n)$ 的理論差距僅約 2.7 倍，若要達到一萬倍以上的效能提升，節點數量必須達到天文數字級別，遠超現有硬體甚至觀測宇宙的範疇。此外，專案宣稱在 800 奈秒內處理完一百萬個節點的數據，被認為在物理層面上幾乎不可能達成，懷疑基準測試可能只是比較了極度優化的路徑與極其低效的 Dijkstra 實作，或是測試流程存在瑕疵。
除了效能數據的爭議，實作過程是否涉及人工智慧輔助也成為焦點。部分資深評論者質疑該程式碼可能是透過 Claude 等大型語言模型生成，並要求作者說明開發過程，以及為何不與現有的成熟演算法庫進行對比，而是僅與作者自製的 Dijkstra 版本比較。然而，也有網友對此持開放態度，認為即便使用了 AI 工具，只要能正確實作頂尖學術論文的成果，對社群仍具備貢獻價值。
在技術細節之外，社群也展開了有趣的理論聯想。有討論者提到 $O(\log^{x/3} n)$ 這種特殊的複雜度形式在整數分解與離散對數演算法（如普通數體篩選法）中也曾出現，猜想不同領域的複雜度陳述背後可能存在某種未被發現的深層聯繫，甚至聯想到數學界的「月光理論」（Monstrous Moonshine），即看似無關的數學領域卻產生了驚人一致的常數或模式。儘管實作的基準測試受到嚴厲審視，但社群普遍認同這類將前沿理論轉化為程式碼的嘗試，對於推動基礎架構的進步具有長遠的正面影響。