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

  • $\begingroup$ 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. $\endgroup$ – chazisop 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.