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

Question

Hello,

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 contains a large number of nodes.

Any advice or comment will be appreciated.

Thank you, Nikola

Answer 1

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.

Answer 2

start BFS for each direct neighbor of the subset. sum BFS depths of each node in subset. choose neighbor that yields smallest sum. Runtime should be O(|subset|*|neighbors|)