需要用算法帮助找到一个DAG中的最大路径 [英] Need assistance with algorithm to find the maximum path in a DAG

问题描述

假如我有这个向无环图（DAG），那里有向边从每个节点（比底部行中的节点以外），以在它下面的两个节点：

Suppose I had this Directed Acyclic Graph (DAG), where there is a directed edge from each node (other than the nodes in the bottom row) to the two nodes below it:

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

我需要通过这个DAG，其中节点权重的总和被最大化找到一个路径。您只能移动对角线左下或右下从这个树中的一个节点。因此，例如，7，3，8，7，5，都会在这棵树的最大路径。

I need to find a path through this DAG where the sum of the nodes' weights is maximized. You can only move diagonally down-left or down-right from a node in this tree. So for example, 7, 3, 8, 7, 5, would give the maximum path in this tree.

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

The input file contains the DAG formatted in this way

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

我的问题是，什么样的算法将是最好找到最大路径和psented在C ++还怎么会这棵树被重新$ P $？

My question is, what algorithm would be best to find maximum path and also how would this tree be represented in C++?

的节点的权重都是非负的。

The node weights are non-negative.

推荐答案

我会重新present这个三角形与 INT 的S向量的向量。

I'd represent this triangle with a vector of vectors of ints.

在底部开始行比较每个adjanced对数字。取更大的一个，并把它添加到数一对以上：

Start at the bottom row and compare each adjanced pair of numbers. Take the bigger one and add it to the number above the pair:

 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.
                    ^  ^

工作的方式到顶部，当你做的，三角形的尖端，将包含最大的一笔。

Work your way to the top and when you're done, the tip of the triangle will contain the largest sum.

这篇关于需要用算法帮助找到一个DAG中的最大路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！