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: 367

Filed under:
|

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

Related posts about algorithm

Related posts about graph