How to recalculate all-pairs shorthest paths on-line if nodes are getting removed?
Posted
by Pavel Shved
on Stack Overflow
See other posts from Stack Overflow
or by Pavel Shved
Published on 2010-03-29T12:39:40Z
Indexed on
2010/03/29
12:43 UTC
Read the original article
Hit count: 366
Latest news about underground bombing made me curious about the following problem. Assume we have a weighted undirected graph, nodes of which are sometimes removed. The problem is to re-calculate shortest paths between all pairs of nodes fast after such removals.
With a simple modification of Floyd-Warshall algorithm we can calculate shortest paths between all pairs. These paths may be stored in a table, where shortest[i][j]
contains the index of the next node on the shortest path between i
and j
(or NULL
value if there's no path). The algorithm requires O(n³) time to build the table, and eacho query shortest(i,j)
takes O(1). Unfortunately, we should re-run this algorithm after each removal.
The other alternative is to run graph search on each query. This way each removal takes zero time to update an auxiliary structure (because there's none), but each query takes O(E) time.
What algorithm can be used to "balance" the query and update time for all-pairs shortest-paths problem when nodes of the graph are being removed?
© Stack Overflow or respective owner