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

Question

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 in a practical way.

Answer 1

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