Finding k-nearest neighbors to a set of nodes in a large graph

Question

Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$.

Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ and $v$ is defined as the length of the shortest path between them. Hence, the lower the distance is, the closer two nodes are.

The 1st nearest neighbor $n\in V$ to the set $S$ has the minimum sum of the distance to all the nodes in $S$.

Finding $n \in V$ to minimize $\Sigma_{s \in S}$ $d(s, n)$

I think solving a unique facility location problem with $S$ as the client nodes can be an answer for the problem when k=1. However, it may not provide a correct answer when k>1 since to the best of my knowledge, if the facilities are more than one, the clients are assumed to be served by their closest facility, so the distance of other facilities are not important if there exists a close facility to a subset of $S$ not all of them. However, I need a ranking of facilities while they consider the sum of the distance to all nodes in $S$ for all $k$ facilities.

Example: 1st facility is the closest one to all nodes in $S$, 2nd is farther than 1st to all in $S$, etc.

Answer 1

You could do $|S|$ iterations of a single-source shortest paths algorithms, one per vertex in $S$, then compute $\sum_{s \in S} d(s,n)$ for each $n \in V$. If all edge lengths are non-negative, the running time to do this using Dijkstra's algorithm will be $O(|S| \cdot |E| + |S| \cdot |V| \log |V|)$. This may be faster than all-pairs shortest paths, particularly if $|S| \ll |V|$.

Answer 2

The Floyd-Warshall algorithm computes all-pair shortest paths in $|V|^3$ time. Then you could compute the "shortest paths" from all nodes in $V$ to the subset $S$ by storing each shortest path in a $|V|$-size array, and sort these distances/array. First $k$ values will give you the $k$-nearest nodes.