In a graph, how to find the nearest node to a group of nodes?

I have an undirected, unweighted graph, which doesn't have to be planar. I also have a subset of graph's nodes (true subset) and I need to find a node not belonging to the subset, with minimum sum of distances to all nodes in the subset.

So far, I have implemented breath-first search starting from each node in the subset, and the intersection that occurs first is the node I am looking for. Unfortunately, it is running too slow since the graph co开发者_如何学Cntains a large number of nodes.

An all-pair shortest path algorithm allows you to find the distance of all nodes to each other in O(V^3) time, see Floyd-warshall. Then summing afterwards will at least be quadratic and I believe worst case cubic as well. It's a very straightforward and not terribly fast way of doing it, but it sounds like it might be an order of magnitude faster than what you're doing right now.