c++ - 需要算法帮助才能找到 DAG 中的最大路径

Question

假设我有这个 Directed Acyclic Graph (DAG) ，其中每个节点(底部行中的节点除外)到其下方的两个节点都有一条有向边:

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

我需要找到一条通过此 DAG 的路径，其中节点的权重之和最大化。您只能从该树中的节点沿对角线向左下或右下移动。因此，例如，7、3、8、7、5 将给出这棵树中的最大路径。

输入文件包含以这种方式格式化的 DAG

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

我的问题是，找到最大路径的最佳算法是什么？这棵树在 C++ 中如何表示？

节点权重是非负的。

Answer 1

我用 int vector 的 vector 表示这个三角形。

从底行开始比较每对相邻的数字。取较大的一个并将其添加到该对上方的数字中:

 5 3             13  3
  \
7 8 6  becomes  7  8  6
^ ^

                  13 3               13 11
                     /
Next iteration   7  8  6   becomes  7  8  6  etc.
                    ^  ^

一直走到顶部，完成后，三角形的尖端将包含最大的总和。