How to compute the critical path of a directional acyclic graph?

Question

What is the best (regarding performance) way to compute the critical path of a directional acyclic graph when the nodes of the graph have weight?

For example, if I have the following structure:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

The critical path should be A->B->F (total weight: 10)

Answer 1

I have no clue about "critical paths", but I assume you mean this.

Finding the longest path in an acyclic graph with weights is only possible by traversing the whole tree and then comparing the lengths, as you never really know how the rest of the tree is weighted. You can find more about tree traversal at Wikipedia. I suggest, you go with pre-order traversal, as it's easy and straight forward to implement.

If you're going to query often, you may also wish to augment the edges between the nodes with information about the weight of their subtrees at insertion. This is relatively cheap, while repeated traversal can be extremely expensive.

But there's nothing to really save you from a full traversal if you don't do it. The order doesn't really matter, as long as you do a traversal and never go the same path twice.

Answer 2

I would solve this with dynamic programming. To find the maximum cost from S to T:

• Topologically sort the nodes of the graph as S = x_0, x_1, ..., x_n = T. (Ignore any nodes that can reach S or be reached from T.)
• The maximum cost from S to S is the weight of S.
• Assuming you've computed the maximum cost from S to x_i for all i < k, the maximum cost from S to x_k is the cost of x_k plus the maximum cost to any node with an edge to x_k.

Answer 3

Try the A* method.

http://en.wikipedia.org/wiki/A*

At the end, to deal with the leaves, just make all of them lead on to a final point, to set as the goal.

Answer 4

There's a paper that purports to have an algorithm for this: "Critical path in an activity network with time constraints". Sadly, I couldn't find a link to a free copy. Short of that, I can only second the idea of modifying http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm or http://en.wikipedia.org/wiki/A*

UPDATE: I apologize for the crappy formatting—the server-side markdown engine is apparently broken.