# Finding the nearest node to a given set of nodes in a graph

I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.

• It would be helpful in answering if you explain what you have tried and know about the problem. (Also see the FAQ for tips about writing a good question.) Apr 21, 2012 at 18:58
• Voted to move to stackoverflow Apr 22, 2012 at 11:12
• related: Eppstein, Wang, Fast Approximation of Centrality arxiv.org/abs/cs/0009005 looks at the case when the set of nodes is all nodes. @chazisop: why? Apr 22, 2012 at 13:22
• While the question is not well posed (no details about the kind of algorithm needed), the problem itself is perfectly on topic: it's a variant of the 1-median problem for a graph. Apr 22, 2012 at 15:38
• It's very likely that by "large graph" the OP meant that the algorithm should use at most quasilinear time and sublinear extra space. It would, of course, be much better if these things would be in the question and we wouldn't have to guess. Apr 22, 2012 at 19:44

• The problem is trivial to solve by computing all-pairs shortest paths (for example, by running Dijkstra at every possible source vertex), followed by $O(n^2)$ post-processing time. But since the question was asked here, as opposed to stackoverflow or cs.SE, I assume the author already knows this. Apr 22, 2012 at 16:24