Теория графов:Нашел Иорданский центр?

Question

Я пытаюсь найти набор вершин, который минимизирует их расстояние до других вершин на взвешенном графе.Основываясь на беглом поиске в Википедии, я думаю, что это называется Иорданский центр.Каковы некоторые хорошие алгоритмы для его поиска?

Прямо сейчас мой план состоит в том, чтобы получить список весов для каждой ветви, исходящей из данной вершины.Центральными будут вершины, веса которых имеют наименьшую относительную разницу.Есть еще какие-нибудь идеи?

Я использую Java, но полезные ответы не обязательно должны быть специфичными для Java.

Answer 1

Я бы хотел сначала использовать Алгоритм Дейкстры (он должен выполняться для каждой вершины) для вычисления кратчайших расстояний между всеми парами вершин - для этого также есть несколько более эффективных алгоритмов, таких как Флойд-Уорсхолл.Затем для каждой вершины V вы должны найти Vm - the самый большой расстояние до любых других вершин зависит от данных, возвращаемых из алгоритма Дейкстры.Тогда вершины с наименьшей виртуальной машиной находятся в центре графика.Псевдокод:

int n = number of verticles;
int[][] D = RunDijkstraOrWarshall()
// D[a,b] = length of shortest path from a to b
int[] Vm = new int[n];
for(int i=0; i<n i++)
{
   Vm[i] = 0
   for(int j=0; j<n; j++) 
   {
     if (Vm[i] < D[i,j]) Vm[i] = D[i,j];
   }  
}

minVm = int.Max;
for(int i=0; i<n ;i++)
{
  if (minVm < Vm[i]) minVm = Vm[i];
}

for(int i=0; i<n ;i++)
{
  if (Vm[i] == minVm)
  {
     // graph center contans i
  }

}

Answer 2

В этой диссертации MSc представлены три алгоритма для задачи центра графов: Распределенный алгоритм для задачи центра графов .

Answer 3

Начиная с версии JGraphT 1.1.0, вы можете просто использовать метод GraphMeasurer.getGraphCenter () . Базовый код использует метод кратчайшего пути. Пользователь может выбрать, какой метод использовать, в зависимости от некоторых характеристик графика (например, разреженный / плотный /...).