Tho*_*mas 10 algorithm graph graph-algorithm
我有一个无向的、正加权的、连接的图，带有 verticesV和边E。我也有一个S顶点子集。现在V包含大约 22000 个顶点和E大约 23000 个边，但是对于更大的输入，这些预计会增加到大约 100 万个。S另一方面，通常包含少于 1000 个顶点，并且它们在图中相对靠近。
我想找到 的“中心” S，意思是一个顶点c，V从它到最远顶点的距离S尽可能小。它就像图中心，但仅适用于顶点的子集。[编辑：] 这也是图形上的1 中心问题；更一般的k 中心问题是 NP-hard 问题，但这个问题可能更容易。
有没有一种算法可以有效地找到这个中心？理想情况下，性能仅取决于S及其周围环境，而不取决于整个图。
我想过开始从所有顶点的广度优先搜索s_i的S同时，当一个顶点停止v_i已经被所有遇到的s_i，但是这是不是太有效。在这种情况下它可能是可行的，但感觉可能有更好的方法。
我不知道如何分析这个算法，也没有引用，但似乎它可能有效。
选择一个起始中心。您当前的近似值应该适用于此。
计算从当前中心到 S 的最短路径树。
修剪树，使所有叶子都属于 S 并计算其中心。
如果这个中心比根好，回到第 2 步。
关于这个算法我可以真正声明的两个形式属性是它总是终止并且它永远不会比起始中心更糟糕（因为如果树的中心不是根，那么它必须是比根更好的中心，因为缺失的边缘可以改善它，但不能改善根）。
为了有效地计算树的中心，在每个节点的所有后代上用到根的最大距离标记每个节点（通过按后序访问节点，在线性时间内）。然后通过具有最大标签的子节点在树中下降，只要它提高半径即可。孩子的子树中的所有东西都会靠近孩子的父边的长度；其他一切都会以相同的数量进一步发展。