现代最短路径算法和图优化技术简述

链接表

摘要和1. 引言

1.1 我们的贡献

1.2 设定

1.3 算法

1. 相关工作

2. 算法

   3.1 结构分解阶段

   3.2 路由阶段

   3.3 WormHole的变体

3. 理论分析

   4.1 预备知识

   4.2 内环的次线性

   4.3 近似误差

   4.4 查询复杂度

4. 实验结果

   5.1 WormHole𝐸, WormHole𝐻和BiBFS

   5.2 与基于索引方法的比较

   5.3 WormHole作为基元：WormHole𝑀

参考文献

2 相关工作

关于最短路径和距离的研究成果浩如烟海，跨越数十年，包括数百种为各种场景设计的算法和启发式方法。在此，我们仅回顾几项与我们工作最密切相关的研究。欲了解更全面的概述，请参阅综述[42, 55]及其中的参考文献。

\ 基于索引的方法。如前所述，一类普遍使用的算法基于地标/草图方法[37, 61, 62]，其中修剪地标标记(PLL)[5]可能是最具影响力的一种。这些算法遵循两步程序：第一步根据重要性（基于不同的启发式方法）生成顶点的排序，第二步根据排序从修剪的最短路径树生成标记。然后，任意一对顶点𝑠和t之间的最短距离可以根据它们的标记快速回答。然而，即使有修剪，PLL也需要大量的设置时间。因此，已有许多尝试对其进行并行化处理[29, 37, 39]。

\ 基于嵌入的方法。一些最近的方法利用图的嵌入来估计最短路径。类似于表示学习，它们寻求找到节点对之间距离的高效表示[64, 65]。现代研究线也考虑图的双曲嵌入，这与树分解密切相关，用于回答最短路径查询[11, 33]。最近的工作还研究了使用基于GPU的深度学习方法来加速这一过程[35, 47, 48]。查询草图[57]考虑了相关但不可比较的任务，即回答最短路径图查询，其目标是计算一个包含给定顶点对之间所有最短路径的子图。他们提出了一种替代标记方案，以提高可扩展性和查询时间。

\

\ 基于核心-边缘的方法。其他几项工作利用了网络的核心-边缘结构[6, 13, 38]。Brady和Cohen[13]使用紧凑路由方案设计了一种基于边缘类似森林的小加性误差算法。Akiba、Sommer和Kawarabayashi[6]利用了核心外部树宽度低的特性，而在[38]中，作者设计了一种基于核心树的索引，以改善大规模图上的预处理时间。我们注意到，在所有这些结果中，内存开销都是超线性的。

\ 最坏情况图。在理论方面，关于最坏情况图中精确和近似最短路径的研究成果众多，例如[19, 20, 22, 49, 51, 67]，最近一年还有改进。这些研究大多集中在2-近似情况，这最早是在Aingworth等人[4]的开创性工作中研究的。我们向读者推荐Zwick的关于精确和近似最短路径算法的综述[66]，以及Sen关于一般图距离预言机的综述[53]，后者强调降低预处理成本。值得注意的是，由于我们做出了超越最坏情况的结构假设（这在大型网络中很常见），即核心-边缘结构，我们的结果和算法与最坏情况理论文献有很大不同。

\

:::info 作者：

(1) Talya Eden，巴伊兰大学 ([email protected])；

(2) Omri Ben-Eliezer，麻省理工学院 ([email protected])；

(3) C. Seshadhri，加州大学圣克鲁兹分校 ([email protected])。

:::

:::info 本论文可在arxiv上获取，采用CC BY 4.0许可证。

:::

\