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 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.