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)

Was it helpful?

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.

OTHER TIPS

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.

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.

My first answer so please excuse for any non-standard thing by the culture of stackoverflow.

I think the solution is simple. Just negate the weights and run the classic shortest path for DAG (modified for weights of vertices of course). It should run fairly fast. (Time complexity of O(V+E) maybe)

I think it should work as when you will negate the weights, the biggest one will become smallest, second biggest will be second smallest and so on as if a > b then -a < -b. Then running DAG should suffice as it will find the solution for the smallest path of the negated one and thus finding longest path for the original one

Try the A* method.

A* Search Algorithm

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

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top