2
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\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, 2016 at 15:41

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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