2009-11-27 8 views
6

Ich versuche, die Menge der Scheitelpunkte zu finden, die ihren Abstand zu anderen Scheitelpunkten in einem gewichteten Diagramm minimiert. Basierend auf einer flüchtigen Wikipedia-Suche, denke ich, dass dies die Jordan Center genannt wird. Was sind einige gute Algorithmen um es zu finden?Graphentheorie: Finden Sie das Jordan Zentrum?

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

Ich verwende Java, aber hilfreiche Antworten müssen nicht unbedingt Java-spezifisch sein.

Antwort

8

Ich werde zuerst Dijkstra algorithm verwenden (es muss für jede vertikale Achse ausgeführt werden), um die kürzesten Abstände zwischen allen Paaren von vertikalen Knoten zu berechnen - es gibt auch einige effizientere Algorithmen wie Floyd-Warshall. Dann müssen Sie für jedes verticle V Vm - den größten Abstand zu irgendwelchen anderen Verticles unter den Daten finden, die vom Dijkstra Algorithmus zurückgereicht werden. Dann sind die Verticles mit dem kleinsten Vm diejenigen in der Graphenmitte. 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 
    } 

}

+0

Ich glaube, du willst "if (Vm [i] Tom

+0

Andere als diese Änderung müssen Sie machen ... gute Erklärung :-). Der Code kann ein bisschen aufgeräumt werden, aber es macht eine gute Arbeit, das Konzept zu illustrieren und zu erklären, was Sie in Worten geschrieben haben :-). +1. – Tom

+0

Danke, dass Sie das bemerkt haben, ich habe gerade die Korrektur vorgenommen. Der obige Algorithmus könnte direkt in Dijksta oder Floyd-Warshal integriert werden, um zu vermeiden, dass zusätzliche For-Schleifen ausgeführt werden (Dijkstra muss ohnehin durch die Vertikalen iterieren). – PanJanek

0

Ab JGraphT Version 1.1.0, können Sie einfach die Methode GraphMeasurer.getGraphCenter() verwenden. Der zugrunde liegende Code verwendet eine Methode für den kürzesten Pfad. Der Benutzer kann abhängig von einigen Merkmalen des Graphen (z. B. spärlich/dicht/...) wählen, welche Methode zu verwenden ist.