Graph longest path

Question

How can I find the longest path in a graph? I thought I can use depth first search but I couldn't find any easier implementation for it ?

Answer 1

As brainjam pointed out in the comments this is NP complete. it is only polynomial if the graph is acyclic. if its a DAG its even linear. again see the wikipage for more info.

Answer 2

try using topological sort for directed graph. it is meant specifically for the purpose of task scheduling...

http://en.wikipedia.org/wiki/Topological_sorting