是否可以对 APSP 问题的任何众所周知的算法(Dijkstra/Floyd-Warshall 等)进行热启动，以减少时间复杂度，并可能减少计算时间？
假设图形由 NxN 矩阵表示。我只考虑一个或多个矩阵条目(<< N)的变化，即相应顶点之间的距离，对算法过程的任何 2 次调用之间的距离。我们是否可以使用第一次调用的解决方案以及对矩阵的增量更改来加速对算法的第二次调用的计算？我主要研究稠密矩阵，但如果有已知的稀疏矩阵方法，请随时分享。谢谢。
最佳答案
我不知道 APSP 的增量算法。但是，有一个用于解决 SSSP 的 A* 增量版本，称为 Lifelong Planning A* (又名“LPA*”，很少也称为“增量 A*”)，这似乎就是您想要的在第二段询问。
关于algorithm - 所有对最短路径 - 热重启？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21619321/