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.

  • 4
    $\begingroup$ 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.) $\endgroup$
    – Kaveh
    Apr 21, 2012 at 18:58
  • $\begingroup$ Voted to move to stackoverflow $\endgroup$
    – chazisop
    Apr 22, 2012 at 11:12
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 22, 2012 at 13:22
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22, 2012 at 15:38
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22, 2012 at 19:44

1 Answer 1


I think Dijkstra's shortest path algorithm would be suitable for your problem. But since you want to find the shortest-path node from a set of nodes and not from just one node, you need to tweak it.

The algorithm is quite straightforward but a bit obtuse, try searching for animated expositions on YouTube.

  • 5
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Apr 22, 2012 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.