Find longest path by number of edges, excluding cycles I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles.

My desired behaviour is: given a graph source and graph sink, find the longest path by number of edges, excluding cycles.

By graph source, I mean a vertex with one or more edges to other vertices and no incoming edges, and the opposite for sink. If there's better terminology, then please let me know about this.

It's important that I'm able to determine what the path is, so I would need an algorithm that can produce a list of edges.

By excluding cycles, this might entail not traversing an edge the process traversed previously.

Do you recognise this algorithm and could you tell me the name, please?

Thanks in advance
The problem you are defining is called Longest Path (and occasionally Longest $s$-$t$-Path) and is NP-complete.

That is, there is an algorithm for solving it, but you shouldn't keep you hopes up when it comes to the running time of the algorithm: it's unlikely to run in polynomial time.

The trivial algorithm is to check for every permutation of the graph, in time $O(d! \cdot 2^{dn})$, but this becomes intractable extremely quickly.  It is possible to bring this down to $O(2^n \cdot \text{poly}(n))$.

You have three options as far as I can see it:


limit the length of the path you need to some reasonable integer $k$ and solve with FPT techniques
use an approximation algorithm
limit the type of input graph to certain smaller and easier graph classes.


Note 1: As Yuval Filmus points out, the problem Longest Path is usually referring to the undirected version.  However, the problem remains NP-complete also in its directed version by a reduction from Directed Hamiltonian Path (Between Two Vertices) (Garey &amp; Johnson, 1979).

Note 2: Yuval Filmus also pointed out that it is solvable in single-exponential time.

Note 3: The problem is solvable in linear time on DAGs, and if you allow repeating edges, the answer is always infinite when your graph has a cycle.