Théorie des graphes: Trouvez le centre Jordan?

Question

J'essaie de trouver l'ensemble des sommets qui minimise leur distance par rapport aux autres sommets d'un graphe pondéré. D'après une recherche rapide dans wikipedia, je pense qu'il s'agit du Centre Jordanien . 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 centraux. D'autres idées?

J'utilise Java, mais les réponses utiles ne doivent pas nécessairement être spécifiques à Java.

Answer 1

Je vais d'abord utiliser l'algorithme de Dijkstra (il doit être exécuté pour chaque verticule) pour calculer les distances les plus courtes entre toutes les paires de sommets - il existe également des algorithmes plus efficaces, comme Floyd-Warshall . Ensuite, pour chaque verticule V, vous devez trouver Vm - la plus grande distance par rapport aux autres verticules parmi les données extraites de l’algorithme de Dijkstra. Ensuite, les verticules avec le plus petit Vm sont celui situé au centre du graphique. 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

Cette thèse de maîtrise contient trois algorithmes pour le problème du centre graphique: Un algorithme distribué pour le problème du centre graphique .

Answer 3

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