Teoría de gráficos: ¿encuentra el centro de Jordan?

Question

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

En este momento, 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 vértices centrales. ¿Alguna otra idea?

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

Answer 1

Utilicé por primera vez Dijkstra algorithm (debe ejecutarse para cada vertículo) para calcular las distancias más cortas entre todos los pares de vertículos; también hay algunos algoritmos más eficientes para eso, como Floyd-Warshall. Entonces, para cada vértice V tiene que encontrar Vm: , la mayor distancia a cualquier otro vértice entre los algoritmos de Dijkstra forma retuidados. Entonces, los vértices con la Vm más pequeña son la que está 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

Tres algoritmos para el problema del centro del gráfico se presentan en esta tesis de maestría: A distributed algorithm for the graph center problem.

Answer 3

A partir de la versión 1.1.0 JGraphT, puede simplemente 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, disperso/denso/...).