Is there a way to determine how the average geodesic distance between nodes of a graph will change just by flipping (1) a single edge without having to traverse the whole graph like in the Djikstra algorithm?


I'm currently doing this by expensively copying the graph, changing the edge, and then calculating the average geodesic distance of the new graph (using Dijkstra's algorithm) and subtracting it from the average geodesic distance of the original graph.. 


Is there a more clever way to to this?


*notes:*


*(1) By flipping a edge I mean the following operation: add the edge if it's absent and remove it if it's present.*


*(2) Good approximations are welcomed. It's part of a Monte Carlo simulation, so I must repeat this calculation many, many times.*



Change in the average geodesic distance of a graph when flipping a single edge
With the right data structures (see <http://www.ams.org/mathscinet-getitem?mr=2145260>), one can maintain a matrix of pairwise distances between vertices in a dynamic graph. Updating the entire matrix after modifying an edge takes $O(n^2\log^3n)$ (amortized). This is at least better than doing a completely new all-pairs shortest path algorithm each time you modify an edge.


I don't, however, see an easy way to take advantage of the fact that you are not interested in the entire matrix of distances, but rather just the average distance.


