Я пытаюсь найти набор вершин, который минимизирует их расстояние до других вершин на взвешенном графе. Основываясь на беглом поиске в Википедии, я думаю, что это называется Jordan Center. Какие есть хорошие алгоритмы для его поиска?
Прямо сейчас мой план состоит в том, чтобы получить список весов для каждой ветви, исходящей из данной вершины. Вершины, веса которых имеют наименьшую относительную разницу, будут центральными. Любые другие идеи?
Я использую Java, но полезные ответы не обязательно должны быть специфичными для Java.
Ответ 1 · рейтинг 8 · PanJanek
Я бы сначала использовал алгоритм Дейкстры (его нужно запускать для каждой вершины) для вычисления кратчайшего расстояния между всеми парами вершин - для этого есть более эффективные алгоритмы, такие как 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
}
}
Ответ 3 · Joris Kinable
Начиная с версии JGraphT 1.1.0, вы можете просто использовать метод GraphMeasurer.getGraphCenter(). Базовый код использует метод кратчайшего пути. Пользователь может выбрать, какой метод использовать, в зависимости от некоторых характеристик графа (например, разреженный/плотный/...).
