Tsinghua Uni Breaks 65-Year Limit: A Faster Alternative to Dijkstra's Algorithm
9 months ago
- #computer-science
- #innovation
- #algorithm
- 清华大学研究人员开发出比迪杰斯特拉算法更快的新算法，打破了65年来的计算屏障。
- 1956年提出的迪杰斯特拉算法一直是解决单源最短路径(SSSP)问题的黄金标准。
- 新算法通过将节点分组聚类并采用偏序处理，绕过了完全排序步骤，实现了O(m·log^(2/3)n)的时间复杂度。
- 该技术可应用于快速导航、网络路由优化、智能AI决策和大规模图数据分析等领域。
- 由于复杂度较高且在小型图上效率较低，日常系统中迪杰斯特拉算法仍具优势。
- 这一突破为图论、AI路径规划和大数据系统开辟了新的研究方向。