标题： 关于从单个源计算前$k$个简单最短路径 显示英文标题

标题： On Computing Top-$k$ Simple Shortest Paths from a Single Source

摘要： 我们研究在加权有向图中计算前$k$个简单最短路径的问题。 虽然单对变体——在两个指定顶点之间找到前$k$个简单最短路径——在过去几十年中已被广泛研究，Yen 算法及其启发式改进已成为最有效的求解策略，但相对较少的关注被投入到更一般的单源版本中，其中目标是确定从源顶点到所有其他顶点的前$k$个简单最短路径。 受排名最短路径众多实际应用的激励，本文我们对该问题提供了新的见解和算法贡献。 具体而言，我们首先给出了其解的结构特性的理论描述。 然后，我们提出了第一个专门设计用于处理该问题的多项式时间算法。 一方面，我们证明了我们的新算法在时间复杂度方面与文献中已知的解决该问题的最佳（且唯一）多项式时间方法相当，即独立地将最快的单对算法应用于源与其余顶点形成的每个顶点对。 另一方面，通过在真实世界和合成图上的大量实验评估，我们证明了我们的算法在运行时间方面始终且显著优于后者基准，实现了高达几个数量级的速度提升。 这些结果确立了我们的新算法作为在实际情况下计算$k$个简单最短路径的首选解决方案。 显示英文摘要

摘要： We investigate the problem of computing the top-$k$ simple shortest paths in weighted digraphs. While the single-pair variant -- finding the top-$k$ simple shortest paths between two specified vertices -- has been extensively studied over the past decades, with Yen's algorithm and its heuristic improvements emerging as the most effective solving strategies, relatively little attention has been devoted to the more general single-source version, where the goal is determining top-$k$ simple shortest paths from a source vertex to all other vertices. Motivated by the numerous practical applications of ranked shortest paths, in this paper we provide new insights and algorithmic contributions to this problem. In particular, we first present a theoretical characterization of the structural properties of its solutions. Then, we introduce the first polynomial-time algorithm specifically designed to handle it. On the one hand, we prove our new algorithm is on par, in terms of time complexity, with the best (and only) polynomial-time approach known in the literature to solve the problem, that is applying the fastest single-pair algorithm independently to each vertex pair formed by the source and the remaining vertices. On the other hand, through an extensive experimental evaluation on both real-world and synthetic graphs, we demonstrate that our algorithm consistently and significantly outperforms the latter baseline in terms of running time, achieving speed-ups of up to several orders of magnitude. These results establish our new algorithm as the solution to be preferred for computing $k$ simple shortest paths from a single source in practical settings.