6

是否可以为 APSP 问题热启动任何众所周知的算法（Dijkstra/Floyd-Warshall 等），以便能够降低时间复杂度，并可能降低计算时间？

假设该图由 NxN 矩阵表示。我只考虑一个或多个矩阵条目（<< N）的变化，即相应顶点之间的距离，在对算法过程的任意 2 次调用之间。我们可以使用第一次调用的解决方案和矩阵的增量更改来加速第二次调用算法的计算吗？我主要看密集矩阵，但如果有已知的稀疏矩阵方法，请随时分享。谢谢。

4

2 回答 2

2

我不知道 APSP 的增量算法。但是，有一个用于解决 SSSP 的增量版本 A*，称为 Lifelong Planning A* （又名“LPA*”，很少也称为“增量 A*”），这似乎是您在第二段中要问的内容。

这是原始论文的链接。您可以在这篇关于 A* 变体的帖子中找到更多信息。

于 2014-02-07T19:29:24.263 回答
1

一篇有趣的研究论文是：动态所有对最短路径算法的实验分析 [Demetrescu, Emiliozzi, Italiano]：

我们展示了针对所有对最短路径问题的动态算法的广泛计算研究的结果。我们描述了我们对 King [18] 以及 Demetrescu 和 Italiano [7] 的最新动态算法的实现，并将它们与 Ramalingam 和 Reps [25] 的动态算法以及随机、真实世界和硬实例上的静态算法进行比较. 我们的实验数据表明，一些动态算法及其算法技术在许多情况下确实具有实用价值。

另一个有趣的分布式算法是Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks [Cicerone, D'Angelo, Di Stefano, Frigioni, Maurizio]：

我们研究了在分布式网络中动态更新所有对最短路径的问题，同时网络发生边缘更新操作。我们考虑动态网络的实际情况，其中一个或多个其他边缘更新正在处理中时可能发生边缘更新。

您可以找到更多资源来搜索动态网络上的所有对最短路径。

于 2014-02-07T19:53:18.610 回答