0

抱歉标题不好。我是图形算法的新手。

我被一个问题困扰了好几天。如果有向无环图的所有节点都被加权，而权重可以是负数，我如何找出权重总和最大的集合？

例如，我们有一个 5 个节点的图 -

  • 节点 1：权重 30，有一条指向节点 4 的边
  • 节点 2：权重 25，边指向节点 4,5
  • 节点 3：权重 -65，没有边缘
  • 节点 4：权重 -20，边到节点 5
  • 节点 5：权重 2，没有边缘

在找出最大点时，例如，如果选择节点 1，则必须选择节点 4 和节点 5（因为它们与节点 1 直接/间接相邻）。

所以我们可以得到的最大点是 - (30-20+2)+(25)=37

对于节点 1 和后代 4,5，然后对于节点 2（不再考虑节点 4,5）

我希望我把我的问题说清楚了。谁能告诉我如何实现这一目标？

4

1 回答 1

0

如果我正确理解了您的问题...您想要的是找到一个节点，该节点使该节点可以达到的值的总和最大化。

这是一些可以为您执行此操作的伪代码

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)
于 2012-04-28T07:10:47.827 回答