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

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

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

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


java graph-theory language-agnostic jgrapht
person Nick Heiner    schedule 27.11.2009    source источник

Ответы (3)


arrow_upward
8
arrow_downward

Я бы сначала использовал алгоритм Дейкстры (его нужно запускать для каждой вершины) для вычисления кратчайшего расстояния между всеми парами вершин — для этого есть более эффективные алгоритмы, такие как Floyd-Warshall. Затем для каждой вершины 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
  }

}

person PanJanek    schedule 27.11.2009
comment
Я полагаю, вы хотите проверить, если (Vm[i] ‹ D[i, j]) Vm[i] = D[i, j]). В вашем случае Vm[i] всегда будет равен нулю. Вы хотите проверить, больше ли расстояние от i до j, чем максимальное расстояние от i до какой-либо другой вершины, которую я видел до сих пор... измените максимальное расстояние так на расстояние от i до j. - person Tom; 27.11.2009
comment
Помимо этого изменения вам нужно сделать... хорошее объяснение :-). Код можно немного подчистить, но он хорошо иллюстрирует концепцию и объясняет словами то, что вы написали :-). +1. - person Tom; 27.11.2009
comment
Спасибо, что заметили это, я только что внес исправление. Приведенный выше алгоритм можно было бы включить прямо в алгоритм Дейксты или Флойда-Уоршала, чтобы избежать дополнительных циклов for (Дейкстра все равно должен перебирать вершины). - person PanJanek; 27.11.2009

arrow_upward
1
arrow_downward

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

person miku    schedule 27.11.2009

arrow_upward
0
arrow_downward

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

person Joris Kinable    schedule 08.09.2017