Finding the hamiltonian path in a directed cyclic graph

i want to know if there is an algorithm to find the longest cyclic path in a directed weighted graph (i think this i a problem of finding the largest Hamiltonian sub-graph).

I need to start from one vertex and return to the same vertex, whit the most possible nodes traversed.



This problem is a special case of the optimal euler circuit problem where all edge weights are 1; the original problem is NP-complete. Moreover, this problem can be used to solve the Hamiltonian Graph problem (a Hamiltonian cycle exists if and only if the optimal circuit traverses all nodes), so it remains NP-complete even with the special case restriction. Any exact solution will (unless P = NP) require exponential time. You may find this paper helpful; it describes a polynomial-time approximation algorithm for this problem, as well as a polynomial-time algorithm for cases where the graph has at most degree 4:

Qiao, Yu. "Optimal Euler Circuit of Maximum Contiguous Cost." IEICE Trans. Fundamentals E90-A, no. 1 (2007): 274-280.

A good approximation gives the Hilbert Curve.


 ? Dijkstra's algorithm to find most weighted path
 ? Dijkstra for longest path in a DAG
 ? How to find the longest path in an acyclic directed graph using OGDF library?
 ? Longest path for weighted directed acyclic graph
 ? In a graph, find longest path with a certain property?
 ? Longest path (edge weight = 1) in Un-directed graph solution?
 ? Floyd-warshall for longest distance for undirected graph
 ? Longest Simple Path In Sparse Cyclic Graphs
 ? Python: Finding the longest path
 ? Longest route in 2D array from max to min