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

Question

我有一个无向的、连通的、正加权的图G = <V,E>。我需要找到一个节点 v_min，V以便v_min最小化与其他节点之间的最大距离。我了解到这是k 中心问题（即k=1）的一个特殊问题，它已知是 NP-Hard。但是，由于我们限制k为等于 1，因此我认为该问题仍然可以有效解决。

我现在的方法是：计算 中节点之间的所有对距离V，例如，使用 Floyd-Warshall，或重复调用 Dijkstra。然后，我们沿着节点列表向下查找使节点与其他节点之间的最大距离最小的节点。如果满足这一条件的节点不止一个，则选择其中任何一个。

1. 这种方法是否正确？
2. 有没有更好的方法（即更有效）？请注意，我对近似算法不感兴趣，只对精确算法感兴趣。

Answer 1

您要查找的节点称为图中心或乔丹中心，查找它们的方法是常用方法。Floyd-Warshall 是一种查找节点之间所有距离的快速方法，并且迭代结果以查找最小最大值将花费更少的时间。

对于大多数用途来说，这应该足够快了，而且不可能做得更好。如果性能是最重要的，你可以看看这篇 2019 年的论文，其中介绍了一种新算法，他们声称该算法具有更好的可并行性，并且通常比 Floyd-Warshall 稍快。