algorithm - 如何选择与图中其他节点的最大最短距离最小的节点？

Question

我有一个无向、连通、正加权的图 G = <V,E> .我要找一个节点 v_min在 V使得v_min之间的最大距离其他节点最小化。我了解到这是k-center 的一个特殊问题。问题(即，与 k=1 )，已知为 NP-Hard。但是，由于我们限制了 k等于1，我假设问题仍然可以有效解决。
我现在的方法是:计算 V 中节点之间的所有对距离，例如，使用 Floyd-Warshall，或重复调用 Dijkstra。然后，我们沿着节点列表向下查找使节点与其他节点之间的最大距离最小的节点。如果满足这一条件的节点不止一个，则选择其中任何一个。

这种方法是否正确？

有没有更好的方法(即更有效)？
请注意，我对近似算法不感兴趣，只对精确算法感兴趣。

Answer 1

您要查找的节点称为 图中心或 乔丹中锋 ，而您找到它们的方法是常用方法。 Floyd-Warshall 是一种快速查找节点之间所有距离的方法，迭代结果以找到最小最大值将花费更少的时间。
对于大多数用途来说，这应该足够快，而且不可能做得更好。如果性能是最重要的，你可以看看 this 2019 paper它引入了一种新算法，他们声称该算法具有更好的并行性，并且通常比 Floyd-Warshall 略快。