Graphentheorie: das Jordan Zentrum Suchen?

Question

Ich versuche, die Menge der Ecken zu finden, die ihren Abstand zu anderen Ecken auf einem gewichteten Graphen minimiert. Basierend auf einer summa wikipedia suchen, denke ich, dass dies der Jordan genannt wird. Was sind einige gute Algorithmen es für die Suche?

Im Moment mein Plan ist, eine Liste des Gewichts für jeden Zweig von einem gegebenen Knoten ausgeht, zu erhalten. Die Eckpunkte, deren Gewichte haben die kleinste relative Differenz werden die zentralen diejenigen sein. Jede andere Ideen?

Ich bin mit Java, aber hilfreichen Antworten müssen nicht unbedingt Java spezifisch sein.

Answer 1

I woluld ersten verwenden Dijkstra-Algorithmus (es hat für jeden verticle ausgeführt werden soll) für computng kürzeste Abstände zwischen allen Paaren von verticles - es gibt auch einige effizienten Algorithmen für die wie Floyd-Warshall . Dann für jede verticle V müssen Sie Vm finden - die größte Abstand zu anderen verticles amongs die Daten retuirned Form Dijkstra-Algorithmus. Dann wird die verticles mit dem kleinsten Vm sind derjenige in dem Grafik-Center. Pseudo-Code:

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

Drei Algorithmen für das Problem Graph Zentrums sind in dieser Masterarbeit präsentiert: ein verteilten Algorithmus für das Problem Graph Zentrums .

Answer 3

Ab JGraphT Version 1.1.0, können Sie einfach die Methode GraphMeasurer.getGraphCenter() verwenden. Der zugrunde liegende Code verwendet eine kürzeste Pfad-Methode. Der Benutzer kann die Methode zu verwenden, in Abhängigkeit von bestimmten Merkmalen des Graphen (z.B. sparse / dicht /...).