6

I have an undirected, connected, positively-weighted graph G = <V,E>. I need to find one node v_min in V such that the maximum distance between v_min and the other nodes are minimized. I've learned that this is a special problem of the k-center problem (i.e., with k=1) which is already known to be NP-Hard. However, since we are restricting k to be equal to 1, I assume that the problem can still be solved efficiently.

The approach I have now is: compute all-pairs distances among the nodes in V, e.g., using Floyd-Warshall, or repeated calls of Dijkstra. Then, we go down the list of nodes to find the one that minimizes the maximum distance between the node and the other nodes. If there are more than one nodes that satisfy this, pick any one of them.

  1. Is this approach correct?
  2. Is there any better approach (i.e., more efficient)? Note that I am not interested in approximation algorithms, only exact algorithms.
Olivier
  • 13,283
  • 1
  • 8
  • 24
spoonboy82
  • 63
  • 4

2 Answers2

4

The nodes you're looking for are called the graph center or the Jordan center, and your approach of finding them is the common method. Floyd-Warshall is a quick way to find all distances between nodes, and iterating over the result to find the minimum maximum will take even less time.

This should be fast enough for most purposes, and it's impossible to do much better. If performance is of the utmost importance, you could take a look at this 2019 paper which introduces a new algorithm which they claim is better parallelizable, and usually slightly faster than Floyd-Warshall.

ADdV
  • 1,162
  • 2
  • 16
0

Speeding up repeated Dijkstra

If you go with repeated Dijkstra for calculating all pairwise distances (which is the more efficient choice for sparse graphs), there is a simple observation that can save you having to perform many of the iterations -- I would expect around half of them, on average.

Because the graph is undirected, once we compute all distances from some root vertex v, we also know the distances from every other vertex to v. Let u be a vertex at maximum distance from v; call this distance d. Then it is not possible for u to be a better choice than v, since all we care about is its maximum distance to any other vertex, and we already know that it is at distance d from some vertex (namely v), so its maximum distance cannot be less than this. So there is no point running a Dijkstra search that starts at u.

IOW, after running Dijkstra from some particular start vertex, we can cross all vertices at maximum distance from it off the list of vertices that we need to run a Dijkstra shortest-path search from. There could be multiple such vertices.

Note that this optimisation doesn't change the asymptotic time complexity, and in the worst case, it saves only 1 iteration (it could be that in each iteration except the first, all maximum-distance vertices have already been processed). But in the best case -- when all vertices are at equal distances from the initially chosen vertex -- we can complete after running just the initial Dijkstra search.

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169