楼主:
yam276 ('_')
2025-08-11 18:38:32清华大学突破Dijkstra算法瓶颈
https://arxiv.org/pdf/2504.17033
Dijkstra算法是找网络中每个点的最短路径时的最经典算法(资工系必学)
自1956年来科学家们遭遇了理论瓶颈:如果想设计解决最短路径问题的最快算法
需先找到距离起点最近的点
这需要按距离排序这些点
这导致算法速度无法快过排序所需时间
在斩获理论计算机国际顶级会议STOC 2025最佳论文奖的作品中
北京清华学者发布不依赖排序的新算法
打破持续数十年Dijkstra算法理论瓶颈
他们用贝尔曼-福特算法定位关键节点后优先探索
接着回溯处理其他边界节点
由于不严格按距离顺序探索每层节点
排序障碍自然失效
若采用恰当分层策略
其速度略超优化版Dijkstra算法
新算法运作效率已远超现有理论极限
任何依赖大量最短路径运算的系统都将受益
这将为资料中心节省大量CPU运算资源