Теория графов: найти центр Иордании?

Question

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

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

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

Answer 1

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

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(). Базовый код использует метод кратчайшего пути. Пользователь может выбрать, какой метод использовать, в зависимости от некоторых характеристик графика (например, разреженный / плотный /...).