グラフ - 正のノードと負のエッジを持つグラフを移動するアルゴリズム

Question

ノードの広告にいくつかの正の値を持つグラフがあり、エッジに負の値があります。私は移動

のためにノードに滞在するとき

• ：私はソース・ノードから宛先ノードに、グラフに正確x回を移動する必要が は
  、目標は、和の合計を最大化することです私が辺を通過するときの減算

したがって、同じノードで移動すると合計が増えます。したがって、値10のノードに4回滞在すると、合計で40が得られます。例は下の画像にあります。この場合

最良の解決策は、次のとおり

Move1 - >（ソースノード+3）3

MOVE2 - >（+ 15 3-20）-2

MOVE3 - >（15滞在）13

...（同じノードを滞在）...

Move19 - >（滞在15）253

Move20 - >（宛先ノード253から5 + 3）251

何の問題を解決するための効率的な解決策になるだろうか？私は擬似コードのようなものを実装できますが、どうすれば解決できるのか理解するだけです。

ありがとうございました。

Answer 1

これは|E|は、エッジの数であるとnはステップ数であるO(|E|*n)時間の複雑さ、で、Bellman-Ford algorithmの変動により解決することができます。

簡単にするために、あなたはまた、すべてのノードでの自己ループを持っていると仮定し、ウェイト0の場合、これは「滞在操作」を表します。 、

今

for all u in V: 
(u,u) in E 
w(u,u) = 0 

をDynamic Programmingを使用して再帰式を適用します：だから、あなたは持っている

D[v][0] = 0   if v is the source 
      -infinity otherwise 
D[v][i] = max { D[u][i-1] + w(u,v) + cost(v) | where (u,v) is an edge } 

ソリューションは、これは基本的に（max代わりのmin付き）ベルマン - フォード法であるD[target][n]

ですしかし、|V|の代わりに、nの反復の後に停止します。