这是Vazirani的《算法》一书中的一个问题
这个问题的输入是在边缘上具有整数权重的树T。权重可以为负，零或正。给出线性时间算法以找到T中最短的简单路径。路径的长度是路径中边缘权重的总和。如果没有重复顶点，则路径很简单。请注意，路径的端点不受限制。 提示：这与在树中找到最大的独立集的问题非常相似。
这个问题的输入是在边缘上具有整数权重的树T。权重可以为负，零或正。给出线性时间算法以找到T中最短的简单路径。路径的长度是路径中边缘权重的总和。如果没有重复顶点，则路径很简单。请注意，路径的端点不受限制。
提示：这与在树中找到最大的独立集的问题非常相似。
如何在线性时间内解决此问题？
这是我的算法，但我想知道它是否是线性时间，因为它与深度优先没有什么不同：
遍历树（深度优先） 保留索引（节点） 添加值 做（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。这是因为您的路径将采用以下基本形状之一：
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]使用所选的前身进行更新。
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]如果pw1[i] !=k。但是，您递归地为所有子代调用该函数。用伪代码看起来像这样：
dw1
i
dw2[i]
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])
