如何选择能够最小化到其他节点的最大最短距离的节点？

Question

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

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

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

1. 此方法是正确的。

2. 对于这个问题，没有更有效的精确算法。

- spoonboy82

Answer 1

你要查找的节点称为图形中心或Jordan中心，你的查找方法是常见的方法。 Floyd-Warshall是查找节点之间所有距离的快速方法，并且迭代结果以查找最小最大值需要更少的时间。

这对于大多数情况来说已经足够快了，而且无法做得更好。如果性能非常重要，你可以查看this 2019 paper，该论文介绍了一种新算法，他们声称该算法更易于并行化，并且通常比Floyd-Warshall略快。

- ADdV

---

谢谢！您的解释和确认正是我所需要的。 - spoonboy82

Answer 2

加速重复的Dijkstra算法

如果您选择使用重复的Dijkstra算法来计算所有成对距离（这是稀疏图的更有效选择），那么有一个简单的观察可以节省许多迭代次数 - 平均而言，我预计会节省约一半的迭代次数。

由于图是无向的，一旦我们计算出从某个根顶点v到所有距离，我们也知道了每个其他顶点到v的距离。让u是距离v最远的顶点;将此距离称为d。然后，u不可能比v更好的选择，因为我们关心的只是它到任何其他顶点的最大距离，而且我们已经知道它与某个顶点（即v）的距离为d，因此其最大距离不能小于此距离。因此，没有必要从u开始运行Dijkstra搜索。

换句话说，在从特定起始顶点运行Dijkstra之后，我们可以将所有最大距离的顶点从需要从中运行Dijkstra最短路径搜索的顶点列表中划掉。可能会有多个这样的顶点。

请注意，这种优化不会改变渐进时间复杂度，在最坏的情况下，只能节省一次迭代（可能是除第一次迭代外，所有最大距离顶点都已经被处理）。但在最好的情况下——当所有顶点与最初选择的顶点的距离相等时——我们可以在运行初始Dijkstra搜索后立即完成。

- j_random_hacker