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?

score 27 · Accepted Answer · answered Mar 26 '10 at 17:30

27

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

answered Mar 26 '10 at 17:30

Larry

4,491
2
24
16

1

This returns just the length of the path. Can the code easily be modified to return the path? – oschrenk Apr 02 '12 at 20:46
1

Yes, the same way with most DP problems -- keep track of the previous and go back on it. – Larry Jul 17 '12 at 16:34
4

`topOrder(G)` is the list of vertices of G in [topological order](https://en.wikipedia.org/wiki/Topological_sorting) – Andre Holzner Oct 29 '16 at 14:22
the loop therefore starts from the 'sources' (no incoming edges) and ends with the 'sinks' (no outgoing edges) – Andre Holzner Oct 29 '16 at 14:57
2

a [paper with same algorithm](http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/Docs/longest-path-in-dag.pdf) but easier to follow the rationale in case you need it. – Andrei-Niculae Petre Apr 19 '17 at 20:16

Can Berk Güder · Answer 2 · 2010-03-26T17:40:05.247

5

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.

edited Mar 26 '10 at 17:40

answered Mar 26 '10 at 17:31

Can Berk Güder

109,922
25
130
137

and do we keep the negative weights as negative ? :p – Hellnar Mar 27 '10 at 00:26
@Hellnar: nope, if you have negative weights in the original graph, they should become positive. w' = -(w) – Can Berk Güder Mar 27 '10 at 09:55

score 2 · Answer 3 · answered Mar 26 '10 at 17:31

2

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.

answered Mar 26 '10 at 17:31

Dan

9,935
15
56
66

score 1 · Answer 4 · answered Mar 16 '13 at 03:02

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.

Longest acyclic path in a directed unweighted graph

4 Answers4

Linked