Is there any algorithm which can find all critical paths in DAG?

Question

I'm writing a paper about some graph algorithms (which are used in CPM), and I need name of some algorithm which can find all critical paths in a DAG. I have looked at Floyd - Warshall algorithm, and I don't know if it could be helpful for finding all of critical paths in a DAG. If critical path and longest path are the same thing, then Floyd - Warshall algorithm could be modified in a way of finding all longest, not shortest, paths in a graph. And even if it can be modified, is there any better way of finding all critical paths?

Answer 1

This can be done with Floyd Warshall by just negating all the weights (since it's a DAG, there won't be any negative cycles). However, Floyd Warshall is O(n^3), while a faster linear time algorithm exists.

From Wikipedia

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.[4] For most graphs, this transformation is not useful because it creates cycles of negative length in −G. But if G is a directed acyclic graph, then no negative cycles can be created, and longest paths in G can be found in linear time by applying a linear time algorithm for shortest paths in −G, which is also a directed acyclic graph.[4] For instance, for each vertex v in a given DAG, the length of the longest path ending at v may be obtained by the following steps:

Find a topological ordering of the given DAG. For each vertex v of the DAG, in the topological ordering, compute the length of the longest path ending at v by looking at its incoming neighbors and adding one to the maximum length recorded for those neighbors. If v has no incoming neighbors, set the length of the longest path ending at v to zero. In either case, record this number so that later steps of the algorithm can access it.

Once this has been done, the longest path in the whole DAG may be obtained by starting at the vertex v with the largest recorded value, then repeatedly stepping backwards to its incoming neighbor with the largest recorded value, and reversing the sequence of vertices found in this way.

Note that finding all longest paths is more problematic since there might be an exponentially large number of them. Therefore there is no worst case efficient way to list them all, though they can easily be enumerated or represented implicitly.

Answer 2

For finding one critical path, Floyd--Warshall with minus weights is markedly inferior to the following folklore (?) algorithm, which computes in linear time the length of the longest path from each vertex.

for vertices v in topological order (sinks before sources):
    set longest-path(v) := the maximum of 0 and length(v->w) + longest-path(w) for all arcs v->w

The Floyd--Warshall version would set longest-path(v) := the maximum of -distance(v, w) for all vertices w after computing the distance array.

To find all of the critical paths, compute the longest-path array and, retaining only those arcs v->w such that longest-path(v) = length(v->w) + longest-path(w), enumerate all paths in the residual DAG using recursion.