algorithm - 如何在图中找到顶点子集的 "center"？

Question

我有一个无向的，正加权的，连通的图，其顶点V和边E。我也有一个顶点的子集S。现在V包含大约22000个顶点，而E包含大约23000个边，但是对于较大的输入，这些值预计将增加到大约一百万。另一方面，S通常包含少于1000个顶点，并且它们在图中相对靠得很近。
我想找到S的“中心”，意思是c中的一个顶点V，从它到S中最远的顶点的距离尽可能小。就像graph center一样，但仅用于一部分顶点。 [编辑:]它也是图形上的1-center problem；更为普遍的k中心问题是NP难题，但这可能更容易。
是否有一种算法可以有效地找到该中心？理想情况下，性能仅取决于S及其周围环境，而不取决于整个图形。
我曾考虑过同时从s_i中的所有顶点S开始广度优先搜索，当所有v_i遇到顶点s_i时停止，但这并不是效率过高。在这种情况下这可能是可行的，但感觉似乎有更好的方法。

Answer 1

我不知道如何分析该算法，也没有引文，但似乎可行。

选择一个起始中心。您当前的近似值应该可以很好地解决此问题。

计算从当前中心到S的最短路径树。

修剪树，以便所有叶子都属于S并计算其中心。

如果此中心比根中心好，请返回到步骤2。

关于此算法，我可以真正声明的两个形式属性是:它总是终止，并且永远不会比起始中心差(因为如果树的中心不是根，那么它必须是比根更好的中心，因为缺少的边缘可以改善它，但不能改善根部)。
为了有效地计算树的中心，请在每个节点的所有后代中以最大距离标记每个节点(在线性时间内，通过按后顺序访问这些节点)。然后通过带有最大标签的子项下降到树中，只要它能改善半径。 child 的子树中的所有内容都将随着 child 的父边缘的长度而变得更近。其他一切都将以相同的数量增长。