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

问题描述

下面是瓦齐拉尼从算法的书有问题

  

输入到这个问题是一个树T与边缘整数权重。权重可以是负的，   零或正。举一个线性时间算法找到最短路径简单的T的长度   路径是在路径的边的权重的总和。路径是简单的，如果没有顶点重复。注意   该路径的端点是不受约束

     

提示：这是非常相似的发现最大的独立集合在一棵树的问题

我该如何解决这个问题的线性时间？

下面是我的算法，但我不知道它是线性的时间，因为它什么比不同深度优先：

  

  
1. 在遍历树（深度优先）
  
2. 在保持指数（节点）
  
3. 添加值
  
4. 请（1），直到树底
  
5. 比较之和打印路径和金额
  

这个问题类似于此<一个href="http://stackoverflow.com/questions/2792865/how-to-minimize-total-cost-of-shortest-path-tree">topic但没有一定的答案。

解决方案

这个问题是pretty的多少等同于的最小和序列问题的，并且可以在通过动态规划以类似的方式来解决。

我们将计算如下阵列使用DF搜索：

  DW1 [I] =最低金额达到只用i节点及其后代。
PW1 [I] = $ P $节点pdecessor ​​i的找到DW1 [Ⅰ]的路径。
DW2 [我] =第二个最低金额achevable只使用节点i及其后代，
         一个路径是边不交相对于发现DW1 [I]的路径。
 

如果你可以计算出这些，需要分（DW1 [K]，DW1 [K] + DW2 [K]）在所有 K 。这是因为你的道路将充分利用这些基本的形状中的一种：

  Kķ
  |要么     /   \
  | / \
  |
 

所有这些都涵盖我们正在采取的款项。

计算DW1

从根节点运行DFS。在DFS，跟踪当前节点及其父亲。在每个节点，假设其子 D1，D2，... DK 。然后 DW1 [I] = MIN（最低{DW1 [D1] +成本[我，D1]，DW1 [D2] +费用[I，D 2]，...，DW1 [DK] +成本[我，DK]}，{最小成本[我，DK]}）。设置 DW1 [I] = 0 的叶节点。不要忘记更新 PW1 [I] 与所选择的predecessor。

计算DW2

从根节点运行DFS。做同样的事情你做了 DW1 ，从节点我将它的一个子<$ C时除外$ C> K ，只更新 DW2 [I] 如果 PW1 [I]！= K 。您调用的函数递归为所有儿童但是。它看起来像这样的伪code：

  DF（节点，父亲）
    DW2 [节点] = INF
    为所有儿童的K节点的
        DF（K，节点）

        如果PW1 [点]！= K
            DW2 [节点] = 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屋！