6

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.

user3282279
  • 61
  • 2
  • I'm rather interested in answers to this question as well, but I think it's better to post it on http://cs.stackexchange.com/ . You might want to provide more details like, whether you are looking at the same source and sink across different calls (in which case I think it might be possible to reuse some values) – yanhan Feb 07 '14 at 06:28
  • Thanks for the tip - I'll post it at the cs stackexchange as well. I am more interested in the general case of determining the distances between all pairs of nodes/vertices in every call( and if possible the least cost path as well). – user3282279 Feb 07 '14 at 14:27
  • 1
    FYI: I noticed the following discussion on cs stackexchange on this topic of dynamic graphs: http://cs.stackexchange.com/q/7250/14479 – user3282279 Feb 07 '14 at 15:07

2 Answers2

2

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.

Community
  • 1
  • 1
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
1

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.

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85