翻转单条边时图的平均测地距离的变化

Question

如果我添加或删除一条比计算前后距离然后减去的速度更快的边，有没有什么方法可以找出图的平均测地距离会改变多少？

我正在对一个系统进行 Metropolis Monte Carlo 模拟，该系统的状态由无向图表示。系统的能量取决于该图的平均测地距离。

在每个蒙特卡罗步骤中，我必须提出对图的修改，然后计算由于该修改而引起的能量变化。我只是选择一个随机边缘并翻转它（如果不存在则添加边缘，如果存在则删除边缘）。我现在所做的是一种蛮力：

Graph = initialize;
L = avgGeodesicLength(Graph)
E0 = energy(L)
for(i = 0; i < mcsteps; i++) {
   newGraph = copy Graph;
   flip a random edge of newGraph;
   L = avgGeodesicLength(newGraph);
   E1 = energy(L);
   dE = E1 - E0
   if (metropolis criteria(dE) is true) {
      Graph = newGraph;
      E0 = E1;
   } 
   else {
      throw the copy away and keep the current state;
   }
}

我宁愿这样做：

Graph = initialize;
L = avgGeodesicLength(Graph);
E0 = energy(L);
for(i = 0; i < mcsteps; i++) {
   edge = random edge of Graph;
   dL = difference in AvgGeodesicLength if I flip edge;
   dE = differenceInEnergy(dL);
   if (metropolis criteria(dE) is true) {
      flip edge; 
      E0 += dE;
   }
   else { do nothing;}
}

如果计算能量差比计算能量本身快得多。如果有一种方法可以计算平均测地线长度的差异，并且给定的边以更快的方式（大 O 方向）翻转，则这是可能的。

有办法做到这一点吗？我知道很难预测单个边缘的变化会影响哪些路径，但是......也许我很幸运！ ：D

编辑：我不在乎我必须为您想到的任何算法使用任何表示形式。如果可以节省我的时间，我愿意这样做。

我的图通常很小（顶点数量通常少于一百个，边数在少数和完全连接之间变化）。问题是我必须重复这个循环很多很多步骤才能达到平衡，并且它们为很多很多不同条件中的每一个计算许多可观测值...:(

编辑2：我不需要单独的测地线路径或其长度，只有平均测地线长度。