How to find a path in graph with maximum edges?

How can I find the longest simple path in a directed, not necessarily acyclic graph?

• There's no start node or goal node- I want the longest contiguous path. It can begin anywhere, can end anywhere as long as the total path is the longest possible. I guess the recurrence for Dynamic Programming would be something like: ds(u,v)=max(ds−1(u,v)+1) d_{s}(u, v) = max(d_{s-1}(u, v) + 1) But I'm having trouble thinking how to code this. Any pointers would be awesome.

• Answer:

  Let f(x) be the longest path ending at node x. Your recurrence is f(x) = 1 + max( f(y) ), where y are all parents of x, or 0 if x has no parent. You can compute this efficiently by traversing the DAG in toposort order, i.e. compute f(x) before f(y) for any (x,y) such that there is an edge from x to y. Edit: The original version of this question was about acyclic graphs. As the question title has changed, this answer is less relevant.