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

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.

StackExchange Computer Science Q#7250, answer score: 18