Teoria dei grafici: trova il centro della Giordania?

Question

Sto cercando di trovare l'insieme di vertici che minimizza la loro distanza dagli altri vertici su un grafico ponderato. Sulla base di una rapida ricerca su Wikipedia, penso che questo sia chiamato Jordan Center . Quali sono alcuni buoni algoritmi per trovarlo?

In questo momento, il mio piano è quello di ottenere un elenco del peso per ciascun ramo emanato da un dato vertice. I vertici i cui pesi hanno la differenza relativa più piccola saranno quelli centrali. Altre idee?

Sto usando Java, ma le risposte utili non devono necessariamente essere specifiche di Java.

Answer 1

Vorrei prima utilizzare Algoritmo di Dijkstra (deve essere eseguito per ogni Verle) per calcolare le distanze più brevi tra tutte le coppie di vertici - ci sono anche alcuni algoritmi più efficienti per quelli come Floyd-Warshall . Quindi per ogni V verticale è necessario trovare Vm - la più grande distanza da qualsiasi altro vertice tra i dati raccolti dall'algoritmo Dijkstra. Quindi, i verticilli con la Vm più piccola sono quelli nel centro del grafico. Pseudocodice:

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

In questa tesi di laurea magistrale sono presentati tre algoritmi per il problema del centro grafico: Un algoritmo distribuito per il problema del centro grafico .

Answer 3

A partire dalla versione 1.1.0 di JGraphT, è possibile utilizzare semplicemente il metodo GraphMeasurer.getGraphCenter () . Il codice sottostante utilizza un metodo di percorso più breve. L'utente può scegliere quale metodo utilizzare, in base ad alcune caratteristiche del grafico (ad esempio sparse / dense / ...).