# Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$.

I need to find a vertex $v \in V$ such that $$\sum_{i=1}^n d(v_i, v)^2$$ is minimal. What is the most time-efficient algorithm to solve this problem? Could I do any better than computing shortest paths from all $v_i$ to all other vertices in the graph?

Real-world example: $n$ friends are looking for a place for a meeting.

This is similar to closeness centrality, but here I have a sum of squared distances rather than sum of distances.

• You are dealing with directed weighted graphs (very general), and it makes it very difficult to find a fast algorithm, unless there is some other constraint such as Euclidean distance, metric space or some other properties? – orezvani May 11 '16 at 5:28
• @emab No special constraints, unfortunately :(... – vojta May 11 '16 at 6:34
• Why not using parallel algorithms? – orezvani May 11 '16 at 6:59
• @emab Which particular algorithm do you mean? Or just compute shortest paths in parallel threads? – vojta May 11 '16 at 12:18
• Without an embedding in $\mathbb{R}^2$, you probably won't be able to get any better than checking all possible paths as you mentioned. – koverman47 Jul 20 '18 at 22:01