所有对最短路径 - 暖启动？

Question

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

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

Answer 1

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

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