algorithm - 如何找到加权树的最短路径？

Question

我有一个加权树，看​​起来像(权重在括号中)

          A1
        /   \
     B1(3)  B2(2)
     /   \  /  \
   C1(1) C2(3) C3(4)
   /   \ /  \  /  \
 D1(8) D2(7) D3(2) D4(5) 
    ......

因此，每个节点都有两个 child 。每个节点与邻居节点共享一个子节点。树的深度可以非常高。

3 + 1 + 8 = 12
3 + 1 + 7 = 11
3 + 3 + 7 = 13 ... and so on

找到最短路径的最佳方法是什么？因此，我不需要权重总和，而是完整路径(比如说 A1-B2-C3-D3)。

如果您能向我推荐正确的算法，我将非常高兴。或者提供 java/伪代码解决方案。

谢谢!

更新

我正在寻找从上到下的完整路径

Answer 1

由于子共享属性，这可能是一个自然的动态规划 (DP) 问题。我建议使用自下而上的DP算法来解决这个问题。

1. 将每个节点的状态定义为 SP(n)，表示从该节点到最短路径。我们可以注意到 SP(n) 仅依赖于 SP(c)，其中 c 是 n 的子节点。并且由于子共享属性，SP(n) 可以被 n 的父级重用。

2. 状态转换方程如下:

   SP(n) = min {for every c of n's children | SP(c) + weight(c)}

至于实现，我们从叶子开始自下而上地扫描以计算 SP(n)，直到我们到达根。时间成本是 O(n)，因为我们在一次运行中计算它。