Partially dynamic efficient algorithms for distributed shortest paths

We study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite) due to the looping and counting infinity phenomena. In this paper, we propose partially dynamic algorithms that are able to concurrently update shortest paths. We experimentally analyze the effectiveness and efficiency of our algorithms by comparing them against several implementations of the well-known Bellman–Ford algorithm.

Authors

• Serafino Cicerone
• Gianlorenzo D’Angelo
• Gabriele Di Stefano
• Daniele Frigioni

Keywords

• Dynamic algorithm
• Distributed algorithm
• Shortest paths