Bon algorithme pour trouver le diamètre d'un graphe (épars) ?

Question

J'ai un grand graphe, connecté, clairsemé, sous forme de liste d'adjacence. Je voudrais trouver deux sommets qui sont aussi éloignés que possible l'un de l'autre, c'est-à-dire l'un de l'autre. diamètre du graphique et deux sommets qui y parviennent.

Je m'intéresse à ce problème dans les cas non dirigés et dirigés, pour différentes applications. Dans le cas dirigé, je m'intéresse bien sûr à la distance dirigée (le plus court chemin dirigé d'un sommet à un autre).

Existe-t-il une meilleure approche que le calcul des plus courts chemins par paires ?

Modifier : Par "aussi éloigné que possible", j'entends bien sûr le "plus long chemin le plus court" -- c'est-à-dire le maximum sur toutes les paires de sommets de la plus courte distance de l'un à l'autre.

Answer 1

J'ai un peu réfléchi au problème, et un peu cherché sur Google, et je suis désolé, mais je n'arrive pas à trouver un algorithme qui ne semble pas être "juste trouver toutes les paires de chemins les plus courts".

Cependant, si vous supposez que Floyd-Warshall est le seul algorithme permettant de calculer une telle chose (Big-Theta de |V|^3), alors j'ai une bonne nouvelle pour vous : L'algorithme de Johnson pour les graphes épars (merci, fidèle CLRS !) calcule toutes les paires de plus courts chemins en (Big-Oh (|V|^2 * lgV + VE)), ce qui devrait être asymptotiquement plus rapide pour les graphes épars.

Wikipedia dit que cela fonctionne pour les réseaux dirigés (je ne suis pas sûr pour les réseaux non dirigés, mais je ne vois pas pourquoi cela ne fonctionnerait pas). lien .

Y a-t-il d'autres éléments du graphe qui pourraient être utiles ? S'il peut être facilement représenté sur un plan 2D (c'est-à-dire s'il est planaire et que les poids des bords obéissent à l'inégalité triangulaire [il se peut qu'il doive satisfaire une exigence plus stricte, je n'en suis pas sûr]), vous pourrez peut-être utiliser des algorithmes géométriques (convex-hull peut fonctionner en nlogn, et trouver la paire de points la plus éloignée est facile à partir de là).

J'espère que cela vous aidera ! - Agor

Edit : J'espère que le lien fonctionne maintenant. Sinon, il suffit de le googler :)

Answer 2

Je ne connais pas de meilleure méthode pour calculer le diamètre autre que tous les plus courts chemins, mais Mathematica utilise l'approximation suivante pour le PseudoDiamètre :

• Une géodésique de graphe est le chemin le plus court entre deux sommets d'un graphe. Le diamètre du graphe diamètre du graphe est la plus longue longueur possible de toutes les géodésiques du graphe. PseudoDiameter trouve un diamètre approximatif du graphe. diamètre du graphe. Il fonctionne en partant d'un sommet u, et trouve un sommet v le plus éloigné de u. Ce processus est répété processus est répété en traitant v comme le nouveau sommet de départ, et se termine lorsque la distance du graphe n'augmente plus n'augmente plus. Un sommet du dernier ensemble ensemble de niveaux qui a le plus petit le plus petit degré est choisi comme sommet de départ final u, et une traversée est pour voir si la distance du graphe peut peut être augmentée. Cette distance du graphe est est considérée comme le pseudo-diamètre.

http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html

Answer 3

Modifier Je me désinsère à nouveau, simplement pour pouvoir continuer à commenter. J'ai quelques commentaires sur l'algorithme de Johnson en dessous de cette réponse. - Aaron

Mon commentaire original : Je suis également curieux de ce problème, mais je n'ai pas de réponse. Il semble lié à la Arbre de répartition minimal (Minimum Spanning Tree) le sous-graphe reliant tous les sommets mais ayant le moins d'arêtes (ou le plus petit poids). C'est un vieux problème avec un certain nombre d'algorithmes, dont certains semblent assez faciles à mettre en œuvre.

J'avais initialement espéré que le diamètre serait évident une fois la MST trouvée, mais je perds espoir maintenant :-( Peut-être que la MST peut être utilisée pour placer une limite supérieure raisonnable sur le diamètre, que vous pouvez utiliser pour accélérer votre recherche du diamètre réel ?

Answer 4

Voici quelques idées pour faire mieux que toutes les paires de chemins les plus courts dans un graphe non orienté, bien que je ne sois pas sûr de l'ampleur de cette amélioration.

Voici une sous-routine qui trouvera deux nœuds distants de D, s'il y en a. Choisissez un nœud arbitraire x et calculez M[x] = la distance maximale de x à tout autre nœud (en utilisant n'importe quel algorithme de plus court chemin à source unique). Si M[x] >= D, alors x est un de nos noeuds et l'autre est facile à trouver. Cependant, si M[x] < D, aucun des points d'extrémité que nous recherchons ne peut être à une distance inférieure à D - M[x] de x (parce qu'il existe des chemins de ce nœud à tous les autres nœuds, via x, de distance < D). Trouvez donc tous les nœuds dont la distance est inférieure à D-M[x] de x et marquez-les comme mauvais. Choisissez un nouveau x, cette fois-ci en vous assurant que vous évitez tous les nœuds marqués comme mauvais, et répétez. Avec un peu de chance, nous marquerons beaucoup de nœuds comme mauvais, ce qui nous permettra d'effectuer beaucoup moins de calculs de plus court chemin que |V|.

Il ne nous reste plus qu'à définir D=diam(G) et à exécuter la procédure ci-dessus. Nous ne savons pas ce qu'est diam(G), mais nous pouvons obtenir une fourchette assez étroite, car pour tout x, M[x] <= diam(G) <= 2M[x]. Choisissez quelques x pour commencer, calculez M[x] pour chacun d'entre eux, et calculez les limites supérieure et inférieure de diam(G) comme résultat. Nous pouvons ensuite effectuer une recherche binaire dans l'intervalle résultant, en utilisant la procédure ci-dessus pour trouver un chemin de la longueur supposée, s'il y en a un.

Bien sûr, il s'agit uniquement de graphes non dirigés. Je pense que l'on pourrait faire un schéma similaire avec des graphes dirigés. Les mauvais nœuds sont ceux qui peuvent atteindre x en moins de D-M[x], et la limite supérieure de diam(G) ne fonctionne pas, il faudrait donc une plage de recherche binaire plus grande.

Answer 5

Pas sûr que ça corresponde au projet, mais intéressant :

HADI : Estimation et extraction rapide de diamètres dans des graphes massifs avec Hadoop

U. Kang, C. Tsourakakis, A. P. Appel, C. Faloutsos, J. Leskovec, "HADI : Fast Diameter Estimation and Mining in Massive Graphs with Hadoop", CMU ML Tech Report CMU-ML-08-117, 2008.