All shortest path pairs - warm restart?

Question

Is it possible to start heating any of the known algorithms (Dijkstra / Floyd-Warshall, etc.) for the APSP problem in order to be able to reduce the time complexity and, possibly, the computation time?

Say the graph is represented by the matrix NxN. I only consider changes to one or more matrix entries (<N), that is, the distances between the corresponding vertices, between any 2 algorithm calls. Can we use the solution from the first call and only incremental changes in the matrix to speed up the calculation of the second call to the algorithm? First of all, I look at dense matrices, but if there are known methods for sparse matrices, feel free to share them. Thanks.

Answer 1

I am not aware of the incremental algorithm for APSP. However, there is an incremental version of A * for the SSSP solution called Lifelong Planning A * (aka 'LPA *,' also rarely called “Incremental A *”), which seems to be what you ask in the second paragraph.

Here is a link to the original paper. You can find more information about this in this A * change post .

Answer 2

Interesting work: Experimental analysis of dynamic shortest path algorithms for all pairs [Demetrescu, Emiliozzi, Italiano] :

We present the results of an extensive computational study of dynamic algorithms for all shortest paths. We describe our implementation of the latest dynamic King algorithms [18] and Demetrescu and Italiano [7], and compare them with the dynamic algorithm of Ramalingam and Reps [25] and static algorithms for random, real and hard cases. Our experimental data show that some dynamic algorithms and their algorithmic methods can be really of practical value in many situations.

Another interesting distributed algorithm is the development of a new algorithm for distributed shortest paths in dynamic networks [Cicerone, DAngelo, Di Stefano, Frigioni, Maurizio]

We study the problem of dynamically updating the shortest paths of pair pairs in a distributed network, while edge updating operations occur with the network. Consider the practical case of a dynamic network in which an edge update can occur when one or more other updates are being processed.

You can find more resources for finding all paired short paths in dynamic networks.