如何在线性时间内找到树中最短的简单路径? [英] How to find the shortest simple path in a Tree in a linear time?

问题描述

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

<块引用>

这个问题的输入是一个边上具有整数权重的树 T.权重可能为负，零，或正.给出一个线性时间算法来寻找 T 中最短的简单路径. a 的长度path 是路径中边的权重之和.如果没有重复顶点，则路径是简单的.笔记路径的端点是不受约束的.

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

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

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

<块引用>

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

这个问题类似于这个主题但是没有确定的答案.

解决方案

这个问题几乎等同于 最小和子序列问题，并且可以通过动态规划以类似的方式解决.

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

dw1[i] = 仅使用节点 i 及其后代可实现的最小总和.pw1[i] = 为 dw1[i] 找到的路径中节点 i 的前驱.dw2[i] = 仅使用节点 i 及其后代可获得的第二个最小总和，相对于为 dw1[i] 找到的路径边缘不相交的路径.

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

 k k|或者   / |/|

所有这些都包含在我们的总和中.

计算 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.但是，您可以为所有子项递归调用该函数.它在伪代码中看起来像这样:

df(节点，父)dw2[节点] = inf对于节点的所有子节点 kdf(k, 节点)如果 pw1[节点] != kdw2[节点] = min(dw2[节点], dw1[k] + 成本[节点, k], 成本[节点, k])

Here is a problem from Algorithms book by 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.

How can I solve this problem in linear time?

Here is my algorithm but I'm wonder if it is linear time since it is nothing different than depth-first:

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

this problem is similar this topic but there is no certain answer.

解决方案

This problem is pretty much equivalent to the minimum sum subsequence problem, and can be solved in a similar manner by dynamic programming.

We will calculate the following arrays by using DF searches:

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

If you can calculate these, take min(dw1[k], dw1[k] + dw2[k]) over all k. This is because your path will take one of these basic shapes:

  k              k
  |     or     /   
  |           /     
  | 

All of which are covered by the sums we're taking.

Calculating dw1

Run a DFS from the root node. In the DFS, keep track of the current node and its father. At each node, assume its children are d1, d2, ... dk. Then dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]}). Set dw1[i] = 0 for leaf nodes. Don't forget to update pw1[i] with the selected predecessor.

Calculating dw2

Run a DFS from the root node. Do the same thing you did for dw1, except when going from a node i to one of its children k, only update dw2[i] if pw1[i] != k. You call the function recursively for all children however. It would look something like this in pseudocode:

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

这篇关于如何在线性时间内找到树中最短的简单路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！