Teoría de la gráfica: encontrar el centro de Jordania?

Question

Estoy tratando de encontrar el conjunto de vértices que minimiza su distancia a otros vértices en un gráfico ponderado. Basándome en una búsqueda superficial de wikipedia, creo que esto se llama Jordan Center . ¿Cuáles son algunos buenos algoritmos para encontrarlo?

Ahora mismo, mi plan es obtener una lista del peso para cada rama que emana de un vértice dado. Los vértices cuyos pesos tienen la menor diferencia relativa serán los centrales. ¿Alguna otra idea?

Estoy usando Java, pero las respuestas útiles no necesariamente tienen que ser específicas de Java.

Answer 1

Primero utilizaría algoritmo Dijkstra (debe ejecutarse para cada artículo) para calcular distancias más cortas entre todos los pares de verticles - también hay algunos algoritmos más eficientes para eso como Floyd-Warshall . Luego, para cada artículo V tiene que encontrar Vm - la distancia más grande a cualquier otra vértice entre los datos retuirned desde el algoritmo Dijkstra. Entonces, los verticles con la Vm más pequeña son los que están en el centro del gráfico. Pseudocódigo:

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

En esta tesis de maestría se presentan tres algoritmos para el problema del centro de gráficos: Un algoritmo distribuido para el problema del centro de gráficos .

Answer 3

A partir de la versión 1.1.0 de JGraphT, simplemente puede usar el método GraphMeasurer.getGraphCenter () . El código subyacente utiliza un método de ruta más corto. El usuario puede elegir qué método usar, dependiendo de algunas características del gráfico (por ejemplo, escaso / denso / ...).