Suppose that I have a undirected and connected graph $G=(E,V)$ where E reperests the set of edges and V reperests the set of nodes. Also I have a set $V_1 \subset V$. My goal is find a node $v_{target} \in V$ to:
$$\min \sum_{v \in V_1}{dis(v_{target},v)}$$
where $dis(v_1,v_2)$ computes the shortest path between $v_1$ and $v_2$.
I have been searching for this problem for a while but found nothing. Does an Algorithm exist for finding out a vertex which is closes to a set of vertices.
Best Answer
A simple approach is to construct a partial shortest-path tree from each node. For each source node, you can apply Dijkstra’s algorithm, terminating early when every node in $V_1$ has been permanently labeled. You can also keep track of the best source node so far and terminate a given source node when the sum to $V_1$ is at least the incumbent value.