问

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

手机用户2502921281_649 发布于 2023-02-12 18:46

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

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

所以,每个节点都有两个孩子.并且每个节点与邻居节点共享子节点.树的深度可以非常高.

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

找到最短路径的最佳方法是什么？因此,我不需要一个权重之和,而是一个完整的路径(比如A1-B2-C3-D3).

如果你能引用我正确的算法,我将非常高兴.或者提供java /伪代码解决方案.

谢谢!

更新

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

1 个回答

由于子共享属性,这可能是自然的动态编程(DP)问题.我建议使用自下而上的DP算法来解决这个问题.
至于实现,我们从叶子自下而上扫描以计算SP(n)直到我们到达根.时间成本是O(n),因为我们在一次运行中计算它.
2023-02-12 18:49 回答

小太郎在路上_439

撰写答案

今天，你开发时遇到什么问题呢？

热门标签