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 paper A New Approach to
Dynamic All Pairs Shortest Paths by Camil Demetrescu and Giuseppe F. Italiano gives a solution to the directed version of the problem. 

It involves saving two priority queues at each position on the matrix and updating and extracting information from these queues as edges are added. The psuedocode for the algorithm is on page 9 of the link.

For undirected graphs like this one, you could add 2 edges for each edge, one in each direction. This will not affect the time complexity of the algorithm.