清华大学交叉信息研究院段然研究组提出无向图单源最短路算法

近日，交叉信息院段然研究组提出新的无向图单源最短路算法，首次在实数边权上突破了Dijkstra算法的排序时限。该论文《A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs》已被FOCS 2023接收。

最短路问题是图论领域最基础的问题之一，单源最短路问题需要找到从一点s到其他所有点的最短路。Dijkstra算法（利用斐波那契堆）的时间复杂度为O(m+n∙log n)，因为Dijkstra算法的副产品是所有点对从s的距离排序，而比较模型下排序需要Ω(n∙log n)时间，所以要改进Dijkstra算法就要避免整体排序。在比较模型下，对于另一个图论基础问题——最小生成树，姚期智院士早在1975年就给出了比排序时间快的算法，而目前已有O(m)时间的随机算法；但对于最短路问题却一直没有突破排序时间的算法。

Dijkstra算法每次从优先级队列（斐波那契堆）中取出目前距离最短的点，然后扫描这个点的边；而新的算法只随机取一部分点放到斐波那契堆中（称为点集R），而其他点v都绑定到离它最近的R点(称为b(v))，并且找到距离v比b(v)更近的所有点，称为Ball(v)。如果R的大小为n/k，则Ball(v)的平均大小为O(k)。（这里m为图的边数、n为点数）

伪代码中relax(v, D)表示如果目前的d(v)>D则更新d(v):=D，并且同时relax(b(v), D+dist(v,b(v))。基于以下两条定理：

● 对R中的点u，从s到u的最短路上不存在点y使得dist(s,b(y))比dist(s,u)长。

● 对其他点v，如果s到v的最短路比dist(s,b(v))+dist(b(v),v)短，并且其经过点y使得dist(s,b(y))≥dist(s,b(v))，那么y到v之间的所有点都在Ball(y)或Ball(v)中。

可以迭代地证明当R中的点u从堆中取出时d(u)已经为实际距离，并且第一个forall循环后所有绑定到u的点v的距离也都被找到。一般地，可以先将图转化为常数度数的稀疏图，则时间复杂度为O(m\sqrt{\log n\log\log n})。

本论文作者为清华大学交叉信息院段然副教授、清华大学交叉信息院博士生毛嘉怡、香港大学博士生、姚班2019届校友束欣凯、清华大学交叉信息院博士生尹龙晖。

论文链接：

https://arxiv.org/abs/2307.04139

FOCS(IEEE Annual Symposium on Foundations of Computer Science) 由IEEE计算机学会的计算机数学基础专委会提供资助，是计算机科学领域最顶级的国际会议，在整个理论计算机科学领域享有崇高的声望，并被公认属于难度最高的会议之一。在本届FOCS会议中，交叉信息院师生共有7篇论文入选。

转自：“创新清华”微信公众号

如有侵权，请联系本站删除！