Dynamically updating shortest paths

Question

I have a graph on which I frequently need to know all shortest paths (or rather their lengths). Because I do not want to recalculate them I store them in a simple array and just retrieve them from there. However since the graph might also change over time I will have to recalculate them at given times.

For now the following changes might happen:

• Adding a node and an edge to it to the graph

• Changing the length of an edge

• Adding a new edge of the graph

• Deleting an edge or deleting a node

In all cases all nodes will always be connected and all edges have positive weights. Also the graph is undirected. The sequence of operations is such, that all nodes will always be from the same component of the graph. If a node or edge is deleted before this other nodes and edges will have been added so that the graph never becomes separated.

For now I am planning to just do the updates and then propagate all the changes through the graph structure. However I am not sure yet how to handle this correctly. How would you try to achieve these updates of the cached length.

EDIT:

As some of you have pointed out it might be neccessary to recalculate everything when a node is added or a link is changed. This might be for example when all distances change through the update. However if I just propagate the changes through the graph and do a relaxation similar to the way it is done dijkstras, I might have to relax the same node multiple times, because I might not choose the optimal order. The question would be how to order the relaxation steps, so I avoid multiple updates as good as possible.

Not sure this makes much sense without the actual idea I have in mind, but I hope this clarifies some more.

Answer 1

You can handle the case where you are deleting an edge/node fairly easily. Just keep track of the actual path between nodes. Then when an edge/node is deleted, go through your paths and see which ones are affected by the change. Recalculate the shortest paths for these.

In the case where you're increasing an edge weight, you can use the same technique.

The other cases are significantly more difficult to deal with. I don't know of any algorithm/data structure that would speed up the recomputation.

Answer 2

The D* family of search algorithms are exactly concerned with the updating of shorting paths in dynamically changing graphs. The algorithms were developed for mobile robot path planning problems. Although the algorithms only return the shortest path from the goal to the current robot location, you might be able to use their bookkeeping and updating rules for all-shortest-paths problems too.