How to compute the critical path of a directional acyclic graph?
algorithm, graph-theory
Solution
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.
Problem
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)