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

Posted by Nikola on Stack Overflow See other posts from Stack Overflow or by Nikola
Published on 2010-05-20T13:28:17Z Indexed on 2010/05/20 13:30 UTC
Read the original article Hit count: 242

Filed under:
|
|
|
|

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

© Stack Overflow or respective owner

Related posts about graph

Related posts about minimum