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

Question

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

The input to this problem is a tree T with integer weights on the edges. The weights may be negative, zero, or positive. Give a linear time algorithm to find the shortest simple path in T. The length of a path is the sum of the weights of the edges in the path. A path is simple if no vertex is repeated. Note that the endpoints of the path are unconstrained.

HINT: This is very similar to the problem of finding the largest independent set in a tree.

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

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

1. Traverse tree (depth-first)
2. Keep the indexes (nodes)
3. add the values
4. do (1) till the end of tree
5. compare the sum and print the path and sum

这个问题类似于这个topic但没有确定的答案。

Answer 1

这个问题几乎等同于 minimum sum subsequence problem , 并且可以用动态规划以类似的方式求解。

我们将使用 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].

如果您可以计算这些，请对所有 k 取 min(dw1[k], dw1[k] + dw2[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] 如果 pw1[i] != k。但是，您可以递归地为所有 child 调用该函数。它在伪代码中看起来像这样:

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])