3

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 ?

Javad
  • 313
  • 3
  • 13
iva123
  • 3,395
  • 10
  • 47
  • 68
  • Are you sure you do not mean the greatest distance between two nodes? – Björn Pollex Mar 27 '10 at 11:49
  • 1
    That may depend on the rules and the characteristics of your graph. Do you allow revisiting nodes? Do you allow retraversing edges? Can the graph be disjoint? Is it directed? Is it acyclic? – Marcelo Cantos Mar 27 '10 at 11:52
  • This seems like a variation on Traveling Salesman. Is it even solvable? – Mike DeSimone Mar 27 '10 at 11:56
  • 1
    Check out this question: http://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph. It refers you to http://en.wikipedia.org/wiki/Longest_path_problem – brainjam Mar 27 '10 at 11:56
  • it's a unweighted and undirected graph sorry for missing information – iva123 Mar 27 '10 at 12:07

4 Answers4

4

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.

Community
  • 1
  • 1
Karussell
  • 17,085
  • 16
  • 97
  • 197
  • 1
    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 Mar 28 '10 at 12:02
1

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

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

Origin
  • 2,009
  • 5
  • 19
  • 19
Shivendra
  • 1,542
  • 2
  • 22
  • 35
1

If its a DAG G=(V,E),you can simple do a topological sort.

Then you mark some node as s and t.

Then you can use dynamic programming where opt(I)= max(opt(j)+1) where j the edge (j,I) is in E.

Just set opt(s)=0 and others to -inf, and ignore nodes before s and after t in the topological sort (you can't reach the this nodes from s, and after you passes t, you can't return).

Note that its work only for a DAG (Directed Acyclic Graph).

Please also note that if its not a DAG, then you can multiply every edge by -1 and then use Bellman Ford, BUT(!) it won't work if you'll have a negative cycle.

Mogsdad
  • 44,709
  • 21
  • 151
  • 275
member555
  • 797
  • 1
  • 13
  • 40
0

save the length/weight of the path between each node as 1/(your integer/double/whatever) and then use the shortest path algorithm

ada
  • 1