Longest acyclic path in a directed unweighted graph

Question

Hello,

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

Thanks

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

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.

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.

Answer 4

Just an idea but can't we use depth first algorithm ? I mean we can get a forest from a graph and choose the longest tree ? sorry it's acyclic : )

Answer 5

This problem is NP-complete. What this means in practice is that for a large random graph there's no known algorithm that can solve this in reasonable time.

If the graph has a special property, like being small, or being acyclic, or alternatively if you just wish to find a long path and not necessarily the longest, then that might be doable.

So find out if any of these cases (or another interesting property) applies and then your refined question might be solvable.