增量式单源最短路径1

增量式单源最短路径（Incremental Single-Source Shortest Paths, ISSSP）问题是一个在图理论和算法设计中常见的动态问题。在这个问题中，我们有一张加权有向图 𝐺=(𝑉,𝐸)，其中节点集合𝑉 和边集合𝐸 可能会经历边的插入和删除操作。给定一个源节点 𝑠 ∈ 𝑉，目标是维护从源节点到图中所有其他节点的距离𝑑(𝑠,𝑡)。 在动态图算法领域，对于精确的动态SSSP和近似完全动态SSSP已经有许多研究，并且通过精细复杂性分析得到了一些强下界。然而，对于有向图的近似部分动态SSSP问题，目前还没有比经典的ES树（ES-Tree）算法效率更高的确定性算法。ES树是由Edmonds和Johnson在1981年提出的，它提供了一种有效的方法来处理动态最短路径问题，但其性能在某些情况下可能不是最优的。 本文提出了一种新的确定性数据结构，用于处理加权有向图中的增量SSSP问题。这个数据结构的总更新时间是 ˜𝑂(𝑛2 log𝑊 /𝜖𝑂(1))，这在非常稠密的图中接近最优，其中 𝑊 是图中最大权重与最小权重的比例。该算法在边数𝑚为𝑛1.1阶时，相对于Henzinger等人在STOC'14和ICALP'15中提出的最佳部分动态随机算法有所改进。 此外，文章还提供了对现有算法的条件性下界。Henzinger等人在STOC'15中利用OMv假设证明了在无向图中，部分动态精确的𝑠-𝑡最短路径问题需要有平均更新或查询时间𝑚1/2−𝑜(1)，前提是允许多项式预处理时间。作者们提出了一个新的关于寻找团（Clique）的假设，从而将具有多项式预处理时间的算法的更新和查询下界提升到𝑚0.626−𝑜(1)。进一步地，基于𝑘-Cycle假设，他们展示了任何部分动态SSSP算法都需要至少这样的时间复杂度。 这篇文章贡献了一个在有向图增量SSSP问题上的突破性算法，提高了效率，并且通过引入新的假设和下界，推动了动态最短路径问题的研究边界。这对于理解动态图算法的潜力以及限制，以及未来算法设计的方向都有着重要意义。