清华大学和斯坦福大学的计算机科学家开发出一种算法，突破了自 1984 年以来限制网络寻路计算的基本速度限制。该团队解决最短路径问题的方法——寻找从网络中一个点到所有其他点的最佳路线——通过避免造成数十年计算障碍的排序过程，运行速度比 Dijkstra 1956 年的算法及其改进算法更快。在清华大学段然的带领下，研究人员将聚类技术与 Bellman-Ford 算法的选择性应用相结合，以识别有影响的节点，而无需按距离对所有路径进行排序。该算法将图分成几层，并使用 Bellman-Ford 算法定位关键交叉点，然后再计算到其他节点的路径。该技术适用于具有任意权重的有向图和无向图，解决了在 20 世纪 90 年代末和 21 世纪初部分突破后一直困扰研究人员的一个问题，该突破仅适用于特定的权重条件。
在 Slashdot 上阅读更多内容。