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.
$\begingroup$
$\endgroup$
6
-
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$– KavehApr 21, 2012 at 18:58
-
$\begingroup$ Voted to move to stackoverflow $\endgroup$– chazisopApr 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$– Radu GRIGoreApr 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$– Suresh VenkatApr 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$– Radu GRIGoreApr 22, 2012 at 19:44
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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