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