Изменение среднего геодезического расстояния графика при перевороте одного ребра

Question

Есть ли способ узнать, насколько изменится среднее геодезическое расстояние графика, если я добавлю или уберу один край, который быстрее, чем вычисление расстояния до и после, а затем вычитание?

Я делаю в Метрополисе Монте-Карло симуляцию системы, состояние которой представлено неориентированным графом. Энергия системы зависит от среднего геодезического расстояния этого графика.

На каждом этапе Монте-Карло я должен предложить модификацию графика, а затем рассчитать изменение энергии в результате этой модификации. Я просто выбираю случайное ребро и переворачиваю его (добавьте ребро, если его нет, уберите ребро, если оно присутствует). То, что я делаю сейчас, - это грубая сила:

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;}
}

, если вычисление разницы в энергии было существенно быстрее, чем вычисление самой энергии. Это возможно, если есть способ рассчитать разницу в средней геодезической длине, если заданное ребро переворачивается намного быстрее (по-крупному).

Есть ли способ сделать это? Я знаю, что трудно предсказать, на какие пути повлияет изменение одного ребра, но ... возможно, мне повезло! : D

РЕДАКТИРОВАТЬ: Мне все равно, какое представление я должен использовать для любых алгоритмов, которые вы имеете в виду. Если это экономит мое время, я готов это сделать.

Мои графы, как правило, немного малы (количество вершин обычно меньше ста, количество ребер варьируется от нескольких до полностью связанных). Проблема в том, что я должен повторить этот цикл для многих, многих шагов, чтобы достичь равновесия, и они вычисляют много наблюдаемых для каждого из многих, многих различных условий ...: (*

РЕДАКТИРОВАТЬ 2: Мне не нужны отдельные геодезические пути или их длины, только средние геодезические длины.