所有对的最短路径-热重启？

Question

是否有可能热启动APSP问题的任何众所周知的算法(Dijkstra/Floyd-Warshall等)，以便能够降低时间复杂度，并潜在地减少计算时间？

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

Answer 1

我不知道APSP的增量算法。但是，有一个增量版本的A*用于求解SSSP，称为终生计划A* (也称为'LPA*‘，很少也称为’增量A*')，这似乎就是您在第二段中所问的问题。

Here是指向原始论文的链接。您可以在this post中找到有关A*变体的更多信息。

Answer 2

一个有趣的研究论文是：

我们给出了所有成对最短路径问题的动态算法的广泛计算研究的结果。我们描述了我们最近的动态算法的实现，并将其与Ramalingam和Rep 25的动态算法以及随机、真实世界和硬实例上的静态算法进行比较。我们的实验数据表明，一些动态算法及其算法技术在许多情况下确实具有实用价值。

另一个有趣的分布式算法是

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

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