<p>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 <em>set</em> of nodes and not from just one node, you need to tweak it.</p>

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

CC BY-SA 3.0
2012-04-22T16:24:48.593Z
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ε
CC BY-SA 3.0
2012-04-22T00:47:03.513Z
2012-04-22T00:47:03.513Z
gfountis
<p>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.</p>

CC BY-SA 3.0
2012-04-21T18:58:38.363Z
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
CC BY-SA 3.0
2012-04-22T11:12:05.013Z
Voted to move to stackoverflow
chazisop
CC BY-SA 3.0
2012-04-22T13:22:41.450Z
related: Eppstein, Wang, _Fast Approximation of Centrality_ http://arxiv.org/abs/cs/0009005 looks at the case when the set of nodes is all nodes. @chazisop: why?
Radu GRIGore
CC BY-SA 3.0
2012-04-22T15:38:32.697Z
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
CC BY-SA 3.0
2012-04-22T17:18:52.990Z
In particular, since there's a trivial poly-time algorithm (as the answers point out), your question must either be asking for something more complicated (fast approximations, lower bounds, etc) or else is not on-scope
Suresh Venkat
CC BY-SA 3.0
2012-04-22T19:44:02.803Z
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
<ds.algorithms><graph-theory><graph-algorithms>
Finding the nearest node to a given set of nodes in a graph
Aadith Ramia
# Finding the nearest node to a given set of nodes in a graph

(Asked by: username_0 on 2012-04-21)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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.)  
> **username_2**: Voted to move to stackoverflow  
> **username_3**: related: Eppstein, Wang, _Fast Approximation of Centrality_ http://arxiv.org/abs/cs/0009005 looks at the case when the set of nodes is all nodes. @username_2: why?  
> **username_4**: 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.  
> **username_4**: In particular, since there's a trivial poly-time algorithm (as the answers point out), your question must either be asking for something more complicated (fast approximations, lower bounds, etc) or else is not on-scope  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_5 on 2012-04-22. Score: -3

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.

> **Comments:**
> **username_6**: 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.  

---

