有向グラフで得られた最大値を計算するアルゴリズムは、nステップ内で

Question

このようになります。 各頂点はi番目のステップで値[i]を持ちます。
（このグラフは、後述の実施例の計算に関連するだけでなく、デモンストレーション、である）

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

この工程は、グローバルなステップです。したがって、ステップ1からステップ2に進むと、配列内のすべての頂点の値インデックスが移動します。

目的は、N個のステップで最大値を得る最大経路を見つけることです。

ので、例えば：1,4,5,2,3

B値の配列：2,1,1

我々は、頂点A、B、C

値配列を有します、5,4

C値アレイ3,2,9,6,1

グラフ：A - > B。 B→C; C - >

N：5（あなたが持っている段階）

最適パス：（常にから開始）

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

値：私たちがしなければ20

が原因

A-> B-> C-> C-> C値のみ18

番目は何ですこれを行うには良いアルゴリズムですか？

ダイクストラはこのようには見えません。

Answer 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 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から始まり、最初のステップは、につながります

第3ステップ：

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)