我有一个加权树,看起来像(权重在括号中)
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/伪代码解决方案。
谢谢!
更新
我正在寻找从上到下的完整路径
最佳答案
由于子进程共享属性,这可能是一个自然的动态规划(DP)问题。我建议使用自下而上的DP算法来解决这个问题。
- 定义每个节点的状态为SP(n),表示从该节点出发的最短路径。我们可以注意到 SP(n) 仅依赖于 SP(c),其中 c 是 n 的子级。并且由于 child 共享属性,SP(n) 可以被 n 的 parent 重复使用。
状态转换方程如下:
SP(n) = min {for every c of n's children | SP(c) + weight(c)}
在实现方面,我们从叶子开始自下而上扫描来计算 SP(n),直到到达根。时间成本是 O(n),因为我们在一次运行中计算它。
关于algorithm - 如何求带权树的最短路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20389166/