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