Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is dynamic? By saying dynamic I mean that we can insert or remove vertices during the execution of the program. I'm trying to find an efficient algorithm for updating the shortest paths from a vertex $v$ to every other vertex $u$, after inserting an edge $e$, without needing to run the shortest path algorithm in the new graph again. How can I do this? Thanks in advance.

  • Note: the changes can be done after the first iteration of the algorithm
  • Note[2]: two nodes are given, $s$ the source and $t$ the target. I need to find the shortest path between these nodes. When the graph is updated I only have to update $\pi(s,t)$, which is the shortest path between $s$ and $t$.
  • Note[3]: I'm only interested in the edge insertion case.

A formal definition: Given a graph $G = (V,E)$. Define an update operation as 1) an insertion of an edge $e$ to $E$ or 2) a a deletion of an edge $e$ from $E$. The objective is to find efficiently the cost of all pairs shortest paths after an update operation. By efficiently, we mean at least better than executing an All-Pairs-Shortest-Path algorithm, such as Bellman-Ford algorithm, after each update operation.


Edit: Below there is a simplified version of the problem:

A weighted graph $G(V,E)$ is given, consisting of unidirectional edges, and two critical vertices $s$ and $t$. A set $C$ of candidate bidirectional edges is also given. I have to build an edge $(u,v) \in C$ to minimize the distance from $s$ to $t$.

share|improve this question
1  
Cool question! I think a helpful distinction might be: Do you want to allow your first iteration of the algorithm to finish before things start changing? Or might you be in the middle of an update as the world is moving around you (scary)? –  usul Dec 8 '12 at 11:36
    
@usul interesting point. The changes can only be done after the first iteration of the algorithm. –  Rondogiannis Aristophanes Dec 8 '12 at 12:06
    
@usul changes during the execution of the algorithm is quite difficult to deal with. I remember that if insertion or deletion of edges is not predictable than it is impossible to solve it correctly. More about that later. I remember I read some papers about this topic once (though I am more intersted in the distributed enviroments - completely different worlds when things get complex like this !) –  AJed Dec 8 '12 at 18:27
    
More clarification questions: Do the endpoints of your path $(u,v)$ stay fixed every time? Are you only interested in the edge-insertion case, or in arbitrary changes in the graph? I would think that there is research answering your question, but unfortunately I don't really know where to look. A quick Google search turns up these slides which seem very helpful, and this paper: "shortest paths on dynamic graphs" (hope the link works). –  usul Dec 8 '12 at 19:11
1  
show 2 more comments

3 Answers

up vote 7 down vote accepted

The problem as you probably have noticed is a quite difficult problem. Checking the web will lead to some complex instances that probably you will not need. Here is a solution - as required (i.e. you dont need to recalculate everything from scratch).

for the case of adding an edge $(u,v)$ - then using your already built-distance matrix - do the following :

For every pair of nodes $x$ and $y$ check if $d((x,u)) + c((u,v)) + d((v,y)) < d((x,y))$ - this can be done in $O(n^2)$ since you are comparing every pair of nodes.

For the case of edge deletion: Given the distance matrix already built, then you can have for every node $u$ a shortest-path tree rooted at $u$. If the deleted edge $e$ is not in that tree, then the shortest paths from $u$ to every other is not affected - (they remain the same).

If $e$ is in the shortest path tree of $u$, then for every node $v$ such that the shortest path $\pi(u,v)$ includes $e$, the paths will change. Therefore, compute the shortest path from $u$ to $v$. Now, repeat the previous for every node -- this is not the best solution. In fact, in its worst case it is asymptotically equivalent to doing every thing from scratch, but can be better on average.

if you want to have better results than this, then have a look at:

  1. Demetrescu, Camil, and Giuseppe F. Italiano. "A new approach to dynamic all pairs shortest paths." Journal of the ACM (JACM) 51.6 (2004): 968-992. (can be found freely from Google)

  2. or have a look at this nicely written survey

share|improve this answer
    
Thanks a lot! You helped very much! –  Rondogiannis Aristophanes Dec 11 '12 at 19:07
    
You re welcome .. i wish i could have helped more –  AJed Dec 11 '12 at 20:04
add comment

The problem you are asking for is a well-known algorithmic problems. It is actually still open, how hard this problem exactly is. Also you should know that there are different incarnations of this problem. In contrast what you are asking for, usually only the distances are returned, whereas you are asking for the the actual shortest paths. Notice that these paths can be already very long. Dynamic graph algorithms distinguish between edge deletions only (decremental dg algorithms), edge insertions only (incremental dg algorithms) and edge insertions and deletions (fully-dynamic dg algorithms). Thus you are interested in incremental algorithms.

The algorithms mentioned in the post of AJed, are slightly outdated. There are newer results by Thorup, see here, on page 8 for a short survey. The currently best fully-dynamic exact APSP algorithm by Thorup (for distance queries, not the path), needs $O(n^2(\log n +\log^2 (1+m/n))$ amortized update time, while supporting $O(1)$ worst case query time. Notice, that if you have $O(n\log n)$ edges, then you could just recompute from scratch with Dijkstra and Fibonacci-heaps and get the same running time as in Thorup's algorithm. So if your graphs are not to dense, I would recommend using Dijkstra.

I am not aware of any better incremental algorithm. But you should do a web search if there exist newer results for this specialized problem.

share|improve this answer
    
I needn't update all the shortest paths in the graph, but only between a given pair $(s,t)$. Is there anything better for that? –  Rondogiannis Aristophanes Dec 9 '12 at 18:40
    
@RondogiannisAristophanes in fact what has been proposed so far is somehow the best. Have a look at this paper which claims that : "the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem." (to be honest, i have read only th intro) - reference: "On dynamic shortest paths problems", Roditty & Zwick -- but would you please tell us what is the exact problem you have ? what specific scenario ? what have you don so far ? -- maybe we can help you better. –  AJed Dec 9 '12 at 19:14
    
@RondogiannisAristophanes the better the performance, the harder it is to implement (in most cases) and sometimes in practical applications you dont need all that much improvement on the performance. –  AJed Dec 9 '12 at 19:15
    
@AJed I edited my post to include a simplified description of the problem. –  Rondogiannis Aristophanes Dec 10 '12 at 15:46
add comment

I believe the AD* algorithm might help you.

http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

When updated information regarding the underlying graph is received, the algorithm incrementally repairs its previous solution. The result is an approach that combines the benefits of anytime and incremental planners to provide efficient solutions to complex, dynamic search problems

AD* highlights: It's "anytime", which means it can give you a "sub-optimal solution" very quickly, though it might not be the best. Given enough time though, it will return the optimal solution. Also, you can restrict the sub-optimal solution to be no worse than the optimal solution by some user-defined constant. This gives you the ability to use this in a real-time planning scenario where having an okay solution (where 'okay' is theoretically bounded) is better than having no solution at all.

http://www.cs.cmu.edu/~maxim/software.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.