I searched in Google and checked similar questions on this site, but couldn't find an answer for my problem. I hope this place is appropriate for my problem.
The problem is formulated as follows:
We are given a weighted digraph with the following properties:
The weights are real numbers
Each vertex has a directed edge into every vertex, but without self-loops (i.e. the graph is complete, each vertex has |V|-1 in and out degree)
The weight for some edge $X \rightarrow Y$ is not necessarily the same as for $Y \rightarrow X$ (therefore we can't treat the graph as an undirected graph)
We are also given a source s and a sink t.
The problem is to find the longest path from s to t.
(Obviously the path should not contain any loops, and can contain at most |V|-1 edges)
Even though the problem is NP-hard and even finding a constant factor approximation is NP-hard for the general case, I wonder if for that kind of graphs we can do better.
The questions are:
Is the problem NP-hard?
If yes, how good can the problem be approximated? I would prefer fast running time over good results.
Do you know any good heuristics for the problem? (that work well in practice)
Any comment/answer/reference is appreciated. Thanks in advance!