Here is an approximation algorithm that should give better results on average than a naive greedy algorithm:
- Consider the graph to be complete - there is an edge between every pair of vertices for a total of
n(n-1)/2
edges. - Sort the edges in descending order of their weights/distances.
- Iterate from the highest distance edge to the lowest distance edge, and remove it if after removing that edge, both its end-points still have degree atleast ceil(n/2) (Dirac's theorem for ensuring a Hamiltonian cycle exists). You could use a stronger result like Ore's theorem to be able to trim even more edges, but the computation complexity will increase.
- In the remaining graph, use a greedy algorithm to find a Hamiltonian cycle. The greedy algorithm basically starts from 1, and keeps selecting the edge with the least distance to a node that does not already form part of the cycle so far. So in your example, it will first pick 1 -> 2, then 2->4, then 4->5 and so on. The last selected vertex will then have a path back to 1.
You could directly use the greedy algorithm given in step 4 on the input graph, but the pre-processing steps 1-3 should in general greatly improve your results on most graphs.