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

Question

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

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

Answer 1

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