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.*