# Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths.

An example is if we have vertices 1 to 5. We can see that initially, all of the paths are infinite except for the diagonal entries, i.e.:

  1 2 3 4 5
1 0 i i i i
2 i 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0


where i means "infinite". But if we add an edge (1, 2) then the 1-2nd and 2-1st entries of the table are updated:

  1 2 3 4 5
1 0 1 i i i
2 1 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0


Now, if we add the edge (2, 3), then obviously the 2-3rd and 3-2nd entires are updated, but also are 1-3rd and 3-1st (which has length 2, since the path is 1->2->3 and 3->2->1):

  1 2 3 4 5
1 0 1 2 i i
2 1 0 1 i i
3 2 1 0 i i
4 i i i 0 i
5 i i i i 0


Now, the more edges and vertices we add, the more complex the problem becomes, since we need to update other entries in the matrix if they are connected. The one fact that I know about this kind of graph is that it is symmetric along the diagonal.

I've been looking at this problem for a few hours and I do not think there is a generic algorithm that will solve the problem for a general unweighted, undirected graph. Are there resources on the problem?

• The i-jth entry should be the length of the shortest path from vertex i to vertex j. Also, for any 2 vertices i and j, there exists at most 1 edge between them. The graph will be guaranteed to not be fully connected. – Ryan Jul 21 '14 at 20:01
• At most 1 edge. All I am looking for is an algorithm that will update a table similar to the one mentioned above. It will not add all possible edges, only edges that I give as input (i.e. I may only add O(n) edges whereas a fully connected graph has O(n^2) edges). – Ryan Jul 21 '14 at 20:10
• No worries! :-) – Ryan Jul 21 '14 at 20:19
• What research have you done? There's been tons of work on dynamic shortest-path algorithms. You've found the right keywords; the word "dynamic" is indeed the critical word. So what research and searching have you done? You should be able to find plenty of work on this subject. For instance, Wikipedia links to citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9856. Searching on this site and on CSTheory.SE immediately turns up cs.stackexchange.com/q/7250/755 and cs.stackexchange.com/q/1521/755 and cstheory.stackexchange.com/q/9990/5038. – D.W. Jul 21 '14 at 22:34