algorithm - 在 n 步内计算有向图中获得的最大值的好算法

Question

问题是这样的:每个顶点在第 i 步都有值 Value[i]。
(此图只是演示，与后面例子的计算无关)

            +----+-----+------+------+-----+-----+-----+----+-----+----  +------+-------+
            |    |     |      |      |     |     |     |    |     |    |      |       |
Value for V1| 2  |  1  |  6   |   4  |    3|   4 |  5  |  1 |   9 | 1  | 10   |   2   |
            |    |     |      |      |     |     |     |    |     |    |      |       |
            +----+-----+------+------+-----+-----+-----+----+-----+----+------+-------+

此步骤是全局步骤。所以当我们从第 1 步转到第 2 步时，其数组中所有顶点的值索引都会移动。

目的是在N步中找到获得最大值的最大路径。

例如:

我们有顶点A,B,C

一个值数组:1,4,5,2,3

B值数组:2,1,1,5,4

C值数组3,2,9,6,1

图:A -> B； B -> C; C -> A

N:5(你有的步骤)

最佳路径:(总是从A开始)

A->B->C->C->A

值:20

因为如果我们这样做

A->B->C->C->C值只有18.

执行此操作的好算法是什么？

Dijkstra 似乎不适合这个。

Answer 1

对于每一步，您都可以找到以特定顶点结束的最佳子路径。

第一步，为每个顶点找到以该顶点结束并通向最大值的子路径。在接下来的步骤中，从这些先前的值开始并重复。子路径(和值)很容易找到，如果您存储每个顶点的前驱:只需选择具有最大值的前驱。

您输入的示例(和自反边):

A values : 1, 4, 5, 2, 3  
B values : 2, 1, 1, 5, 4  
C values : 3, 2, 9, 6, 1  
A successors : A, B
B successors : B, C
C successors : A, C
A predecessors : A, C
B predecessors : A, B
C predecessors : B, C

从 A 和值 1 开始，第一步导致:

A max : 5 (subpath A->A)
B max : 2 (subpath A->B)
C max : 0 (no subpath)

第二步:

A max : 10 (subpath A->A->A)    <- the predecessors of A are A and C,
                                   and the previous max value of A
                                   is greater than that of C.
B max : 5 (subpath A->A->B)
C max : 11 (subpath A->B->C)

第三步:

A max : 13 (subpath A->B->C->A)
B max : 15 (subpath A->A->A->B)
C max : 17 (subpath A->B->C->C)

第四步也是最后一步:

A max : 20 (path A->B->C->C->A)
B max : 19 (path A->A->A->B->B)
C max : 18 (path A->B->C->C->C)