Retrieving the shortest path of a dynamic graph

Question Detail: 

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

Asked By : Rontogiannis Aristofanis

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7250

Answered By : AJed

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