具有加权边的树的中心（可能为负）

Question

对于未加权的树和具有正边权重的树，我之前见过这个问题，但还没有看到对于可能具有负权重的树的解决方案。

作为参考，树的中心定义为与任何其他顶点的最大距离最小的顶点。

Answer 1

和边权为正的树的动态规划解完全一样。让我们运行深度优先搜索两次（我们可以选择任意顶点作为根）。在第一阶段，我们将计算 distIn(v) = the longest distance from v to a vertex from the v's subtree. 我认为这部分是微不足道的（如果需要我可以详细说明）。在第二阶段，我们将为所有 v 计算不在 v 子树内的最远顶点。我们称它为 distOut(v)。这是它的伪代码：

void computeDistOut(v, pathFromParent) 
    distOut(v) = pathFromParent
    childDists = empty list
    for c : children of v
        childDists.add(distIn(c) + cost(v, c))
    for c : children of v
        maxDist = max among all distances from childDists except (distIn(c) + cost(v, c))
        computeDistOut(c, max(pathFromParent, maxDist) + cost(v, c))

每个顶点的最大距离为max(distIn(v), distOut(v))。现在我们可以选择一个最小化该值的顶点（根据定义它是一个中心）。

关于时间复杂度：这个方案如果实现得当，是线性的。我们可以只在其中存储两个最大值，而不是维护所有 children（伪代码中的 childDists）的距离列表。它允许我们在 O(1) 中获得 maxDist 值（它是第一个或第二个最大值）。

具有加权边的树的中心（可能为负）

Center of tree with weighted edges (possibly negative)

algorithm

graph

tree

graph-algorithm

weighted