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: 239
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