How do I find the path with the biggest sum of weights in a weighted graph?

I have a bunch of objects with level, weight and 0 or more connections to objects of the next levels. I want to know how do I get the "heaviest" path (with the biggest sum of weights).

I'd also love to know of course, what books teach me how to deal with graphs i开发者_StackOverflown a practical way.

Your graph is acyclic right? (I presume so, since a node always points to a node on the next level). If your graph can have arbritrary cycles, the problem of finding the largest path becomes NP-complete and brute force search becomes the only solution.

Back to the problem - you can solve this by finding, for each node, the heaviest path that leads up to it. Since you already have a topological sort of your DAG (the levels themselves) it is straighfoward to find the paths:

1. For each node, store the cost of the heaviest path that leads to it and the last node before that on the said path. Initialy, this is always empty (but a sentinel value, like a negative number for the cost, might simplify code later)

2. For nodes in the first level, you already know the cost of the heaviest path that ends in them - it is zero (and the parent node is None)

3. For each level, propagate the path info to the next level - this is similar to a normal algo for shortest distance:

   for level in range(nlevels):
       for node in nodes[level]:
           cost = the cost to this node
            for (neighbour_vertex, edge_cost) in (the nodes edges):
                alt_cost = cost + edge_cost
                if  alt_cost < cost_to_that_vertex:
                    cost_to_that_vertex = alt_cost
   

My book recommendation is Steve Skiena's "Algorithm Design Manual". There's a nice chapter on graphs.

I assume that you can only go down to a lower level in the graph.

Notice how the graph forms a tree. Then you can solve this using recursion:

heaviest_path(node n) = value[n] + max(heaviest_path(children[n][0]), heaviest_path(children[n][1]), etc)

This can easily be optimized by using dynamic programming instead.

Start with the children with the lowest level. Their heaviest_path is just their own value. Keep track of this in an array. Then calculate the heaviest_path for then next level up. Then the next level up. etc.

The method which i generally use to find the 'heaviest' path is to negate the weights and then find the shortest path. there are good algorithms( http://en.wikipedia.org/wiki/Shortest_path_problem) to find the shortest path. But this method holds good as long as you do not have a positive-weight cycle in your original graph.

For graphs having positive-weight cycles the problem of finding the 'heaviest' path is NP-complete and your algorithm to find the heaviest path will have non-polynomial time complexity.