如何在线性时间内找到树中最短的简单路径？

Question

这是Vazirani的算法书中的一个问题

该问题的输入是树T,边缘上具有整数权重.权重可以是负数,零或正数.给出线性时间算法以找到T中最短的简单路径.路径的长度是路径中边缘权重的总和.如果没有重复顶点,则路径很简单.请注意,路径的端点不受约束.

提示:这与在树中查找最大独立集的问题非常相似.

如何在线性时间内解决这个问题？

这是我的算法,但我想知道它是否是线性时间,因为它与深度优先没什么不同:

1. 遍历树(深度优先)
2. 保留索引(节点)
3. 添加值
4. 做(1)直到树的尽头
5. 比较总和并打印路径和总和

这个问题与此主题类似,但没有确定的答案.

Answer 1

该问题几乎等同于最小和子序列问题,并且可以通过动态编程以类似的方式解决.

我们将使用DF搜索计算以下数组:

dw1[i] = minimum sum achievable by only using node i and its descendants.
pw1[i] = predecessor of node i in the path found for dw1[i].
dw2[i] = second minimum sum achevable by only using node i and its descendants,
         a path that is edge-disjoint relative to the path found for dw1[i].

如果你可以计算这些,min(dw1[k], dw1[k] + dw2[k])接管所有k.这是因为您的路径将采用以下基本形状之一:

  k              k
  |     or     /   \
  |           /     \
  | 

所有这些都包括在我们正在采取的总和中.

计算dw1

从根节点运行DFS.在DFS中,跟踪当前节点及其父节点.在每个节点,假设它的子节点d1, d2, ... dk.然后dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]}).dw1[i] = 0为叶节点设置.不要忘记pw1[i]使用选定的前任更新.

计算dw2

从根节点运行DFS.做同样的事情dw1,除非从一个节点i转到其中一个孩子k,只更新dw2[i]if pw1[i] != k.然而,您可以递归地为所有孩子调用该函数.伪代码看起来像这样:

df(node, father)
    dw2[node] = inf
    for all children k of node
        df(k, node)

        if pw1[node] != k
            dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])