<p>The search keywords are "dynamic all pairs shortest paths".</p>

<p>Demetrescu and Italiano have a good survey,
<a href="http://dl.acm.org/citation.cfm?id=1198519" rel="nofollow">http://dl.acm.org/citation.cfm?id=1198519</a></p>

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

CC BY-SA 3.0
2016-03-26T17:44:48.610Z
2016-03-26T17:44:48.610Z
Chad Brewbaker
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>What is the fastest algorithm for this problem so far?</p>

<p>Thank you very much</p>

CC BY-SA 3.0
2016-03-23T15:41:25.230Z
I found this related [question](http://cs.stackexchange.com/questions/7250/retrieving-the-shortest-path-of-a-dynamic-graph). Although the poster asks information for all-pairs shortest path, the answers and references should prove at least to be a good starting point.
chazisop
<graph-algorithms>
Finding the shortest distance in a dynamic graph
mommomonthewind
# Finding the shortest distance in a dynamic graph

(Asked by: username_0 on 2016-03-23)

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

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: I found this related [question](http://cs.stackexchange.com/questions/7250/retrieving-the-shortest-path-of-a-dynamic-graph). Although the poster asks information for all-pairs shortest path, the answers and references should prove at least to be a good starting point.  

---

## 1 answers

### Answer by username_2 on 2016-03-26. Score: 2

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.


---

