# 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.) – Kaveh Apr 21 '12 at 18:58
• Voted to move to stackoverflow – chazisop Apr 22 '12 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? – Radu GRIGore Apr 22 '12 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. – Suresh Venkat Apr 22 '12 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. – Radu GRIGore Apr 22 '12 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. – Jeffε Apr 22 '12 at 16:24