How do I select the node that minimizes the maximum shortest distance to the other nodes in a graph?

Question

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.

Answer 1

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.