假设我有这个有向无环图 (DAG) http://en.wikipedia.org/wiki/Directed_acyclic_graph，其中从每个节点（底行中的节点除外）到其下面的两个节点都有一条有向边：
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++ 中表示这棵树？
节点权重是非负的。
我用向量的向量来表示这个三角形ints.
从底行开始，比较每对相邻的数字。取较大的一个并将其添加到该对上方的数字中：
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.
^ ^
一直走到顶部，完成后，三角形的尖端将包含最大的和。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
