28
$\begingroup$

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$.

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
15
$\begingroup$

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 don't 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

Improve this answer
$\endgroup$
0
18
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Rontogiannis Aristofanis
    Dec 9, 2012 at 18:40
  • $\begingroup$ @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. $\endgroup$
    – AJed
    Dec 9, 2012 at 19:14
  • $\begingroup$ @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. $\endgroup$
    – AJed
    Dec 9, 2012 at 19:15
  • $\begingroup$ @AJed I edited my post to include a simplified description of the problem. $\endgroup$
    – Rontogiannis Aristofanis
    Dec 10, 2012 at 15:46
5
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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