5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. While this is a correct answer, it might be a baseline algorithm to solve the problem due to its complexity. I'm more interested in approximation or using some variants of the facility-location problem, k-median problem, etc (if we can get rid of "minimizing the distance to its nearest facility part") in order to use off-the-shelf solutions provided for them. $\endgroup$ – mhn_namak Aug 13 '17 at 0:59
1
$\begingroup$

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|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.