Théorie des graphes: Trouver le centre Jordan?

Question

J'essaie de trouver l'ensemble des sommets qui minimise leur distance aux autres sommets sur un graphe pondéré. Basé sur une recherche rapide wikipedia, je pense que cela s'appelle le Jordan Center. Quels sont les bons algorithmes pour le trouver?

À l'heure actuelle, mon plan est d'obtenir une liste du poids de chaque branche émanant d'un sommet donné. Les sommets dont les poids ont la plus petite différence relative seront les plus centraux. D'autres idées? J'utilise Java, mais les réponses utiles n'ont pas nécessairement besoin d'être spécifiques à Java.

Answer 1

Je voudrais d'abord utiliser Dijkstra algorithm (il doit être exécuté pour chaque verticle) pour calculer les plus courtes distances entre toutes les paires de verticles - il y a aussi des algorithmes plus efficaces pour cela comme Floyd-Warshall. Ensuite, pour chaque verticille V, vous devez trouver Vm - la plus grande distance à d'autres verticles parmi les données retirées de l'algorithme de Dijkstra. Ensuite, les verticles avec le plus petit Vm sont ceux du centre du graphe. Pseudocode:

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

Trois algorithmes pour un problème de centre de graphes sont présentés dans cette thèse MSc: A distributed algorithm for the graph center problem.

Answer 3

À partir de la version 1.1.0 JGraphT, vous pouvez simplement utiliser la méthode GraphMeasurer.getGraphCenter(). Le code sous-jacent utilise une méthode de chemin d'accès le plus court. L'utilisateur peut choisir la méthode à utiliser, en fonction de certaines caractéristiques du graphique (par exemple, clairsemé/dense/...).