Longest acyclic path in a directed unweighted graph

Question

What algorithm can be used to find the longest path in an unweighted directed acyclic graph?

Textualism

Answer 1

Dynamic programming. It is also referenced in Longest path problem, given that it is a DAG.

The following code from Wikipedia:

algorithm dag-longest-path is
    input: 
         Directed acyclic graph G
    output: 
         Length of the longest path

    length_to = array with |V(G)| elements of type int with default value 0

    for each vertex v in topOrder(G) do
        for each edge (v, w) in E(G) do
            if length_to[w] <= length_to[v] + weight(G,(v,w)) then
                length_to[w] = length_to[v] + weight(G, (v,w))

    return max(length_to[v] for v in V(G))

Salaam

This returns just the length of the path. Can the code easily be modified to return the path? – Aaronaaronic

Yes, the same way with most DP problems -- keep track of the previous and go back on it. – Salaam

topOrder(G) is the list of vertices of G in topological order – Timekeeper

the loop therefore starts from the 'sources' (no incoming edges) and ends with the 'sinks' (no outgoing edges) – Timekeeper

a paper with same algorithm but easier to follow the rationale in case you need it. – Stilliform

Answer 2

As long as the graph is acyclic, all you need to do is negate the edge weights and run any shortest-path algorithm.

EDIT: Obviously, you need a shortest-path algorithm that supports negative weights. Also, the algorithm from Wikipedia seems to have better time complexity, but I'll leave my answer here for reference.

Cantrell

and do we keep the negative weights as negative ? :p – Textualism

@Hellnar: nope, if you have negative weights in the original graph, they should become positive. w' = -(w) – Charie

Answer 3

Wikipedia has an algorithm: http://en.wikipedia.org/wiki/Longest_path_problem

Looks like they use weightings, but should work with weightings all set to 1.

Fargone

Answer 4

Can be solved by critical path method:
1. find a topological ordering
2. find the critical path
see [Horowitz 1995], Fundamentals of Data Structures in C++, Computer Science Press, New York.

Greedy strategy(e.g. Dijkstra) will not work, no matter:1. use "max" instead of "min" 2. convert positive weights to negative 3. give a very large number M and use M-w as weight.

Sibell