Longest path in a cyclic, directed and weighted graph
Longest Path is NP-hard; the reduction from Hamiltonian Path is almost trivial.

That means that we do not know any algorithm with even polynomial running-time. You have to compromise.

Of course, the problem is easier for special classes of graphs, for instance both undirected and directed acyclic graphs.