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 '12 at 18:58
  • $\begingroup$ Voted to move to stackoverflow $\endgroup$ – chazisop Apr 22 '12 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$ – Radu GRIGore Apr 22 '12 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$ – Suresh Venkat Apr 22 '12 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$ – Radu GRIGore Apr 22 '12 at 19:44

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.

| cite | improve this answer | |
  • 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 '12 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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