J'essaie de trouver l'ensemble de sommets qui minimisent leur distance avec d'autres sommets sur un graphique pondéré. Basé sur une recherche curseure Wikipedia, je pense que cela s'appelle le Jordan Center . Quels sont certains 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 centrales. Toute autre idée?
J'utilise Java, mais des réponses utiles ne doivent pas nécessairement être spécifiques à Java.
3 Réponses :
Trois algorithmes de graphique Problème sont présentés dans cette thèse MSC: Un algorithme distribué pour le problème du centre de graphique .
i woluld d'abord utiliser Dijkstra algorithme (il doit être couru pour chaque verticule) Pour calculer les distances les plus courtes entre toutes les paires de verticles - il existe également des algorithmes plus efficaces pour ceux-ci comme Floyd-Warshall . Ensuite, pour chaque verticule V, vous devez trouver vm - la la plus grande distance à tout autre vertical de l'algorithme de Dijkstra. Ensuite, les verticles avec le plus petit VM sont celui du centre graphique. Pseudocode: }
Je crois que vous voulez vérifier "si (vm [i]
Autre que ce changement, vous devez faire ... bonne explication :-). Le code peut être nettoyé un peu, mais cela fait un bon travail d'illustration du concept et d'expliquer ce que vous avez écrit en mots :-). +1.
Merci d'avoir tapé cela, je viens de faire la correction. L'algorithme ci-dessus pourrait être incorporé directement à Dijksta, ou Floyd-Warshal pour éviter de faire fonctionner des boucles supplémentaires (Dijkstra doit faire part à des verticoles de toute façon).
À partir de JGRAPHT Version 1.1.0, vous pouvez simplement utiliser la méthode graphmeasier.getgraphger () . Le code sous-jacent utilise une méthode de chemin la plus courte. L'utilisateur peut choisir quelle méthode à utiliser, en fonction de certaines caractéristiques du graphique (par exemple, SPARSE / DENSE /...). / P>