Graphentheorie: Finden Sie das Jordan Zentrum?

Question

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?

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.

Answer 1

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 
    } 

}

Answer 2

In dieser Masterarbeit werden drei Algorithmen für das Graphzentrumsproblem vorgestellt: A distributed algorithm for the graph center problem.

Answer 3

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.