How to find out maximum points possible from a directed acyclic graph?

0
votes

Sorry the title was no good. I am new to graph algorithms.

I'm stuck with a problem for several days. If all the nodes of a directed acyclic graph are weighted, while the weight can be negative, how can I find out a set for which the sum of the weights is maximum?

for example, we have a graph of 5 nodes-

  • node 1 : weight 30, has a edges directed to node 4
  • node 2 : weight 25, has edges directed to nodes 4,5
  • node 3 : weight -65, no edges from it
  • node 4 : weight -20, edge to node 5
  • node 5 : weight 2, no edge from it

while finding out the maximum points, say, if node 1 is chosen, node 4 and as well as 5 must be chosen(as they are directly/indirectly adjacent from node 1).

so maximum point we can have is- (30-20+2)+(25)=37

for node 1 and descendant 4,5, and then for node 2(node 4,5 not considered anymore)

I hope I made my problem clear. Can anybody tell me how I can achieve this?

1
graph
I'm afraid it's not entirely clear. The objective is to choose a set of starting nodes, such that the sum of the weights of those starting nodes and all additional nodes reachable from that starting set is maximum? – Jeffrey Hantin
No it's not a homework. I tried to solve a graph relation problem, found out the SCC's of the graph and had to apply this on those connected sets. – crysoberil
@Jeffrey Hantin : No you can choose any combination of the verteces, while making sure summation of the points is maximum. – crysoberil

1 Answers

0
votes

If I understand your question correctly... What you want is to find a node that maximizes the sum of values that that node can reach.

Here is some psuedo-code that would do this for you

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)