# Retrieving the shortest path of a dynamic graph

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

-
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. – Rontogiannis Aristofanis 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

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

-
Thanks a lot! You helped very much! – Rontogiannis Aristofanis Dec 11 '12 at 19:07
You re welcome .. i wish i could have helped more – AJed Dec 11 '12 at 20:04

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.

-
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? – Rontogiannis Aristofanis 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. – Rontogiannis Aristofanis Dec 10 '12 at 15:46