How to calculate the critical path of a directed acyclic graph?

Question

What is the best way (relative to performance) for calculating the critical path of an acyclic direction 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 don't have a clue about critical paths, but I guess you mean this .

Finding the longest path in an acyclic graph with weights is only possible by moving the entire tree and then comparing the lengths, since you never know how the rest of the tree is weighted. You can find more about tree traversal on Wikipedia . I suggest that you go with a preliminary round as it is easy and simple to implement.

If you are going to frequently query, you can also increase the boundaries between nodes with information about the weight of their subtrees when inserting. This is relatively cheap, and re-crawling can be extremely expensive.

But you have nothing to save you from a complete detour if you do not. Order is not a big deal if you go around and never go the same way twice.

Answer 2

I would solve this using 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 reach from T.)
• The maximum cost from S to S is the weight of S.
• Assuming you calculated 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 for any node with an edge to x_k.

Answer 3

There is a document in which there is an algorithm for this: "The critical path in a network of actions with time constraints." Unfortunately, I could not find a link to a free copy. In short, I can only sharpen the idea of ​​changing http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm or http://en.wikipedia.org/wiki/A *

UPDATE: I apologize for the crap formatting - the server side markup mechanism seems to be broken.

Answer 4

My first answer, please excuse any non-standard thing for the stackoverflow culture.

I think the solution is simple. Just deny the weights and run the classic shortest path for the DAG (of course, for the vertex weights). It should work pretty fast. (Perhaps the time complexity is O (V + E))

I think this should work as if you had lost weight, the largest would be the smallest, the second largest would be the second smallest, and so on, as if a > b then -a < -b . Then the execution of the DAG should be sufficient, since it will find a solution for the smallest path of negation and, thus, find the longest path for the original

Answer 5

Try method A *.

A * Search Algorithm

In the end, to deal with the leaves, just do everything so that they reach the end point to set a goal.