How can we find a longest path in a graph ?? I thought we can use depth first but I couldn't find any easier implemantation for it ?
A:
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.
Karussell
2010-03-27 22:54:06
for a rather simple planar graph it is very easy to implement to get all paths (=> get the longest path). look here: http://stackoverflow.com/questions/2500877/count-of-distinct-acyclic-paths-from-aa-b-to-ac-d/2532646#2532646(and just use the path which is the longest) this should give you an idea of how one could do it with a general graph: just iterate over all edges of the current vertex instead of the 4 nextCell() calls
Karussell
2010-03-28 12:02:09