Dans un graphique, comment trouver le nœud le plus proche d'un groupe de nœuds?

Question

J'ai un graphique non-orienté, non-pondéré, qui n'a pas besoin d'être planaire. J'ai également un sous-ensemble de noeuds de graphe (sous-ensemble vrai) et j'ai besoin de trouver un noeud n'appartenant pas au sous-ensemble, avec la somme minimum de distances à tous les noeuds dans le sous-ensemble. Jusqu'ici, j'ai mis en œuvre une recherche inspiratoire à partir de chaque nœud du sous-ensemble, et l'intersection qui se produit en premier est le nœud que je recherche. Malheureusement, il fonctionne trop lentement car le graphe contient un grand nombre de nœuds.

Answer 1

Un algorithme de chemin le plus court pour toutes les paires vous permet de trouver la distance de tous les nœuds l'un à l'autre en temps O (V^3), voir Floyd-warshall. Ensuite, la somme après sera au moins quadratique et je crois que le pire cas cubique aussi. C'est une façon très simple et pas très rapide de le faire, mais il semble que ce soit un ordre de grandeur plus rapide que ce que vous faites en ce moment.