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

问题描述

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

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

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

这个问题类似于此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

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:

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

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