有向非循環グラフから最大点を見つける方法は？

Question

申し訳ありませんがタイトルは良くありませんでした。私はグラフアルゴリズムに新しいです。

私は数日間問題を抱えています。有向非循環グラフのすべてのノードが重み付けされている場合、重みは負になりますが、重みの合計が最大となる集合を見つけるにはどうすればよいでしょうか？

は、例えば、我々は5 nodes-

• ノード1のグラフである：体重30を、ノード2
• ノード4への有向エッジを有する：体重25、エッジは、ノード4に向けられました5
• ノード3：重量-65、それからのNO縁
• ノード4：重量-20、ノードへのエッジ5
• ノード5：重量2、NOエッジそれから

例えば、ノード1が選択された場合、（ノード1から直接的または間接的に隣接するように）ノード4および5も選択されなければならないという最大点を見出しながら、

を見つける。我々が有することができる

ように最大点は - （30-20 + 2）+（25）=ノード1および子孫4,5 37

、次いでノード2（ノード4,5のためではありませんもう考慮する）

私は私の問題を明確にしたいと思う。どのように私はこれを達成することができる誰も教えてくれる？

Answer 1

あなたの質問が正しく理解されたら...あなたが望むのは、そのノードが到達できる値の合計を最大にするノードを見つけることです。ここで

はあなた

def maxVertex(Vertices): 
    for vertex in reversed_topological_sorted(Vertices): 
     vertex.value = vertex.weight 
     if vertex.neighbors: 
       vertex.value += sum(other_vertex.value for other_vetrex in vertex.neighbors) 

    return max(Vertices,key=lambda vertex: vertex.value)