All pairs shortest path - warm restart?

Question

Is it possible to warm start any of the well known algorithms (Dijkstra/Floyd-Warshall etc) for the APSP problem so as to be able to reduce the time complexity, and potentially the computation time?

Let's say the graph is represented by a NxN matrix. I am only considering changes in one or more matrix entries( << N), i.e. distance between the corresponding vertices, between any 2 calls to the algorithm procedure. Can we use the solution from the first call and just the incremental changes to the matrix to speed up the calculation on the second call to the algorithm? I am primarily looking at dense matrices, but if there are known methods for sparse matrices, please feel free to share. Thanks.

Answer 1

I'm not aware of an incremental algorithm for APSP. However, there is an incremental version of A* for solving SSSP called Lifelong Planning A* (aka 'LPA*,' rarely also called 'Incremental A*'), which seems to be what you're asking about in the second paragraph.

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

Answer 2

An interesting study paper is: Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms [Demetrescu, Emiliozzi, Italiano]:

We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [18] and of Demetrescu and Italiano [7], and compare them to the dynamic algorithm of Ramalingam and Reps [25] and to static algorithms on random, real-world and hard instances. Our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.

Another interesting distributed algorithm is Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks [Cicerone, D’Angelo, Di Stefano, Frigioni, Maurizio]:

We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing.

You can find more resources searching for All Pairs Shortest Paths on Dynamic Networks.