# Finding the shortest distance in a dynamic graph

I have a non-weighted directed graph G with edges E and vertices G. Edges can be added or removed, and therefore vertices can be added.

For instance, if I have a graph with 4 nodes: 0, 1, 2, 3 and if I add the edge 3 -> 4, it means the node 4 will be added. Nodes cannot be removed.

I am studying the problem of determining the shortest distance (just distance, not path) in this dynamic graph. I am very newbie in this problem, but as I know it would be still an open problem.

What is the fastest algorithm for this problem so far?

Thank you very much

• I found this related question. Although the poster asks information for all-pairs shortest path, the answers and references should prove at least to be a good starting point. Mar 23 '16 at 15:41

The search keywords are "dynamic all pairs shortest paths".

Demetrescu and Italiano have a good survey, http://dl.acm.org/citation.cfm?id=1198519

Looks like $O(n^2 log^3 n)$ cost per update if you want to maintain fast lookups.