На графике, как найти ближайший узел к группе узлов?

Question

У меня есть неориентированный, невзвешенный график, который не должен быть плоским. У меня также есть подмножество узлов графа (истинное подмножество), и мне нужно найти узел, не принадлежащий подмножеству, с минимальной суммой расстояний до всех узлов в подмножестве.

До сих пор я реализовал поиск по первому дыханию, начиная с каждого узла в подмножестве, и пересечение, которое происходит первым, - это узел, который я ищу. К сожалению, он работает слишком медленно, так как граф содержит большое количество узлов.

Answer 1

Алгоритм кратчайшего пути для всех пар позволяет найти расстояние между всеми узлами за O (V ^ 3) времени, см. Floyd-warshall . Тогда последующее суммирование будет, по крайней мере, квадратичным, и я считаю, что и в худшем случае кубическим. Это очень простой и не очень быстрый способ сделать это, но похоже, что он может быть на порядок быстрее, чем то, что вы делаете сейчас.